二元搜尋樹

二元搜尋樹表現出特殊的行為。一個節點的左子必須具備值小於它的父代值，並且節點的右子節點的值必須大於它的父值。

二元搜尋樹表示

我們將使用節點物件來實現樹，並通過參照連線它們。

基本操作

以下是遵循樹的基本操作。

• 搜尋 ? 搜尋一棵樹中的元素。

• 插入 ? 插入元素到一棵樹中。

• 前序遍歷 ? 遍歷一棵樹方法。

• 後序遍歷 ? 遍歷樹在序方法。

• 後序遍歷 ? 遍歷樹的後序方法。

節點

限定了具有一些資料，參照其左，右子節點的節點。

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};

搜尋操作

每當一個元素是被搜尋。開始從根節點搜尋，如果資料小於鍵值，在左子樹中搜尋元素，否則搜尋元素在右子樹。每一個節點按照同樣的演算法。

struct node* search(int data){
   struct node *current = root;
   printf("Visiting elements: ");
	
   while(current->data != data){
      if(current != NULL) {
         printf("%d ",current->data);
			
         //go to left tree
         if(current->data > data){
            current = current->leftChild;
         }//else go to right tree
         else{                
            current = current->rightChild;
         }
			
         //not found
         if(current == NULL){
            return NULL;
         }
      }			
   }
   return current;
}

插入操作

每當一個元素將被插入。首先找到它應有的位置。開始從根節點搜尋，如果資料小於鍵值，搜尋空位置在左子樹那麼插入資料。否則，搜尋空位置在右子樹並插入資料。

void insert(int data){
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty
   if(root == NULL){
      root = tempNode;
   }else{
      current = root;
      parent = NULL;

      while(1){                
         parent = current;
			
         //go to left of the tree
         if(data < parent->data){
            current = current->leftChild;                
            //insert to the left
            if(current == NULL){
               parent->leftChild = tempNode;
               return;
            }
         }//go to right of the tree
         else{
            current = current->rightChild;
            //insert to the right
            if(current == NULL){
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}