【C++】Binary Search Tree

Binary Search Tree的优势在于寻找、插入的时间複杂度较低，它只需要O(log n)~

Binary Search Tree的特性如下~ 若树的节点不为空~

左子树的所有节点的值要小于它的父节点的值~

右子树的所有节点的值均大于它的父节点的值~

学习目标: Binary Search Tree的概念及实务

学习难度: ☆☆★

Linked List Version

#include<iostream>using namespace std;struct Node //节点的结构{int data;Node* Left;Node* Right;};Node* GetNode(int data) //实体化节点{    Node* newNode=new Node();    newNode->data=data;    newNode->Left=newNode->Right=NULL;    return newNode;}Node* Insert(Node* node,int data) //插入节点{if(node==NULL){node=GetNode(data);}else if(data>node->data){node->Right=Insert(node->Right,data);}else if(data<node->data){node->Left=Insert(node->Left,data);}return node;}void Preorder(Node* node) //前序走访{if(node){cout<<node->data;Preorder(node->Left); Preorder(node->Right); }}void Inorder(Node* node) //中序走访{if(node){Inorder(node->Left);                 cout<<node->data;Inorder(node->Right); }}void Postorder(Node* node) //后序走访{if(node){Postorder(node->Left);         Postorder(node->Right);                 cout<<node->data;}}int main(){    Node* node= NULL; //初始化node        node=Insert(node,0); node=Insert(node,1);node=Insert(node,2);node=Insert(node,3);Preorder(node);}

Array Version

#include <iostream>#include <cstring>using namespace std;char btree[1024];void preorder(int);  /*初始化函式, 方可让main调用, 因为程式是结构式的*/void inorder(int);   /*初始化函式, 方可让main调用, 因为程式是结构式的*/ void postorder(int); /*初始化函式, 方可让main调用, 因为程式是结构式的*/ int main(void){  memset(btree,0,sizeof(btree)); /*将btree中sizeof(btree)的值给定为0*/    /*使用1当起始地址, 因为后面走访需要基于起始地址去判断*/    btree[1]='A';    btree[2]='B';    btree[3]='C';    btree[4]='D';    btree[5]='E';    btree[6]='F';    preorder(1);    cout << endl;    inorder(1);    cout << endl;    postorder(1);    cout << endl;}void preorder(int p){  if(btree[p])   {    cout << btree[p];        preorder(2*p);        preorder(2*p+1);  }}void inorder(int p){  if(btree[p])  {    inorder(2*p);        cout << btree[p];        inorder(2*p+1);  }  }void postorder(int p){ //简而言之, 深度走完, 在依序走      if(btree[p])   {    postorder(2*p);        postorder(2*p+1);        cout << btree[p];  }}

参考资料:

https://zh.wikipedia.org/zh-tw/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9