樹(二元樹)


樹表示由邊緣連線的節點。我們將要具體地討論二元樹或二元搜尋樹。

二元樹是用於資料儲存目的的特殊的資料結構。二元樹有一個特殊的情況,每個節點可以有兩個子節點。二元樹有序陣列和連結串列的兩個好處,搜尋排序在陣列插入或刪除操作一樣快的,在連結串列也是盡可能快。

樹(二叉樹)

術語

以下是關於樹的重要方面。

  • 路徑 ? 路徑是指沿一棵樹的邊緣節點的序列。

  •  ? 節點在樹的頂部被稱為根。有每棵樹只有一個根和一個路徑從根節點到任何節點。

  • 父子點 ? 除根節點的任何一個節點都有一個邊緣向上的節點稱為父節點。

  • 子節點 ? 給定節點的邊緣部分連線向下以下節點被稱為它的子節點。

  • 葉子點 ? 節點不具有任何子節點被稱為葉節點。

  • 子樹 ? 子樹代表一個節點的後代。

  • 存取 ? 存取是指檢查某個節點的值在控制的節點上時。

  • 遍歷 ? 遍歷意味著通過節點傳遞一個特定的順序。

  • 層次 ? 一個節點的層次表示的節點的產生。如果根節點的級別是0,那麼它的下一子結點為1級,其孫子是2級等。

  •  ? 鍵表示基於一個節點在其上的搜尋操作將被進行了一個節點的值。

二元搜尋樹表現出特殊的行為。一個節點的左子的值必須低於其父的值,節點的右子節點的值必須大於它的父節點的值。

二元搜尋樹表示

Binary Search Tree

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

基本操作

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

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

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

  • 前序遍歷 ? 遍歷樹前序方法

  • 中序遍歷 ? 遍歷樹在序方法

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

節點

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

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;
            }
         }
      }            
   }
}        

前序遍歷

這是一個簡單的三個步驟。

  • 存取根結點
  • 遍歷左子樹
  • 遍歷右子樹
void preOrder(struct node* root){
   if(root != NULL){
      printf("%d ",root->data);
      preOrder(root->leftChild);
      preOrder(root->rightChild);
   }
}

中序遍歷

這是一個簡單的三個步驟。

  • 遍歷左子樹
  • 存取根結點
  • 遍歷右子樹
void inOrder(struct node* root){
   if(root != NULL){
      inOrder(root->leftChild);
      printf("%d ",root->data);          
      inOrder(root->rightChild);
   }
}

後序遍歷

這是一個簡單的三個步驟。

  • 遍歷左子樹
  • 遍歷右子樹
  • 存取根結點
void postOrder(struct node* root){
   if(root != NULL){            
      postOrder(root->leftChild);
      postOrder(root->rightChild);
      printf("%d ",root->data);
   }
}

演示程式

TreeDemo.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

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

struct node *root = NULL;

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;
            }
         }
      }            
   }
}

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 preOrder(struct node* root){
   if(root != NULL){
      printf("%d ",root->data);
      preOrder(root->leftChild);
      preOrder(root->rightChild);
   }
}

void inOrder(struct node* root){
   if(root != NULL){
      inOrder(root->leftChild);
      printf("%d ",root->data);          
      inOrder(root->rightChild);
   }
}

void postOrder(struct node* root){
   if(root != NULL){            
      postOrder(root->leftChild);
      postOrder(root->rightChild);
      printf("%d ",root->data);
   }
}

void traverse(int traversalType){
   switch(traversalType){
      case 1:
         printf("\nPreorder traversal: ");
         preOrder(root);
         break;
      case 2:
         printf("\nInorder traversal: ");
         inOrder(root);
         break;
      case 3:
         printf("\nPostorder traversal: ");
         postOrder(root);
         break;
   }            
}  

int main() {
   /*                     11               //Level 0
   */
   insert(11);
	
   /*                     11               //Level 0
   *                      |
   *                      |---20           //Level 1
   */
   insert(20);
	
   /*                     11               //Level 0
   *                      |
   *                  3---|---20           //Level 1
   */
   insert(3);  
	
   /*                     11               //Level 0
   *                      |
   *                  3---|---20           //Level 1
   *                           |
   *                           |--42       //Level 2
   */
   insert(42);
	
   /*                     11               //Level 0
   *                      |
   *                  3---|---20           //Level 1
   *                           |
   *                           |--42       //Level 2
   *                               |
   *                               |--54   //Level 3
   */
   insert(54);
	
   /*                     11               //Level 0
   *                      |
   *                  3---|---20           //Level 1
   *                           |
   *                       16--|--42       //Level 2
   *                               |
   *                               |--54   //Level 3
   */
   insert(16);
	
   /*                     11               //Level 0
   *                      |
   *                  3---|---20           //Level 1
   *                           |
   *                       16--|--42       //Level 2
   *                               |
   *                           32--|--54   //Level 3
   */
   insert(32);
	
   /*                     11               //Level 0
   *                      |
   *                  3---|---20           //Level 1
   *                  |        |
   *                  |--9 16--|--42       //Level 2
   *                               |
   *                           32--|--54   //Level 3
   */
   insert(9);
	
   /*                     11               //Level 0
   *                      |
   *                  3---|---20           //Level 1
   *                  |        |
   *                  |--9 16--|--42       //Level 2
   *                     |         |
   *                  4--|     32--|--54   //Level 3
   */
   insert(4);
	
   /*                     11               //Level 0
   *                      |
   *                  3---|---20           //Level 1
   *                  |        |
   *                  |--9 16--|--42       //Level 2
   *                     |         |
   *                  4--|--10 32--|--54   //Level 3
   */
   insert(10);

   struct node * temp = search(32);
   if(temp != NULL){
      printf("Element found.\n");
      printf("( %d )",temp->data);
      printf("\n");
   }else{
      printf("Element not found.\n");
   }

   struct node *node1 = search(2);
   if(node1 != NULL){
      printf("Element found.\n");
      printf("( %d )",node1->data);
      printf("\n");
   }else{
      printf("Element not found.\n");
   }        

   //pre-order traversal
   //root, left ,right
   traverse(1);
	
   //in-order traversal
   //left, root ,right
   traverse(2);
	
   //post order traversal
   //left, right, root
   traverse(3);       
}

如果我們編譯並執行上述程式,那麼這將產生以下結果 -

Visiting elements: 11 20 42 Element found.(32)
Visiting elements: 11 3 Element not found.

Preorder traversal: 11 3 9 4 10 20 16 42 32 54 
Inorder traversal: 3 4 9 10 11 16 20 32 42 54 
Postorder traversal: 4 10 9 3 16 32 54 42 20 11