在码农港湾
做一个实实在在的内行人

树(二叉树)

树表示由边缘连接的节点。我们将要具体地讨论二叉树或二叉搜索树。

二叉树是用于数据存储目的的特殊的数据结构。二叉树有一个特殊的情况,每个节点可以有两个子节点。二叉树有序数组和链表的两个好处,搜索排序在数组插入或删除操作一样快的,在链表也是尽可能快。

树(二叉树)

术语

以下是关于树的重要方面。

  • 路径 − 路径是指沿一棵树的边缘节点的序列。
  •  − 节点在树的顶部被称为根。有每棵树只有一个根和一个路径从根节点到任何节点。
  • 父子点 − 除根节点的任何一个节点都有一个边缘向上的节点称为父节点。
  • 子节点 − 给定节点的边缘部分连接向下以下节点被称为它的子节点。
  • 叶子点 − 节点不具有任何子节点被称为叶节点。
  • 子树 − 子树代表一个节点的后代。
  • 访问 − 访问是指检查某个节点的值在控制的节点上时。
  • 遍历 − 遍历意味着通过节点传递一个特定的顺序。
  • 层次 − 一个节点的层次表示的节点的产生。如果根节点的级别是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

码农刷题必备工具 VS 码农进阶必读书籍

IT面试宝典宝典書城