【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