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