数据结构&算法 树

  • 表示通过边连接的节点。我们将专门讨论二叉树或二叉搜索树。二叉树是用于数据存储目的的特殊数据结构。二叉树有一个特殊条件,即每个节点最多可以有两个孩子。二叉树既有序数组又有链表的好处,因为搜索与排序数组一样快,插入或删除操作也与链表一样快。
    tree
  • 重要概念

    以下是关于树的重要术语。
    • 路径 - 路径是指沿着树边缘的节点序列。
    • - 树顶部的节点称为根。每棵树只有一个根,并且从根节点到任何节点只有一条路径。
    • 父节点 - 除根节点外的任何节点都具有一个称为父级的节点的上边缘。
    • 子节点 - 给定节点下方通过其边缘向下连接的节点称为其子节点。
    • 叶子 - 没有任何子节点的节点称为叶子节点。
    • 子树 - 子树表示节点的后代。
    • 访问 - 访问是指在控件位于节点上时检查节点的值。
    • 遍历 - 遍历是指以特定顺序通过节点。
    • 级别 - 节点的级别表示节点的生成。如果根节点处于级别0,则其下一个子节点处于级别1,其子代处于级别2,依此类推。
    • keys - key表示节点的值,基于该值将对节点执行搜索操作。
  • 二叉搜索树的表示

    二进制搜索树表现出特殊的行为。节点的左子节点的值必须小于其父节点的值,并且节点的右子节点的值必须大于其父节点的值。
    tree
    我们将使用节点对象来实现树,并通过引用将它们连接起来。
    编写树节点的代码与下面给出的代码相似。它有一个数据部分,并引用了它的左右子节点。
    
    struct node {
       int data;   
       struct node *leftChild;
       struct node *rightChild;
    };
    
    在树中,所有节点共享相同的结构。
  • 二叉搜索树的基本操作

    可以对二进制搜索树数据结构执行的基本操作如下:
    • 插入 -在树中插入元素/创建树。
    • 搜索 -搜索树中的元素。
    • 预定遍历 -以预定方式遍历一棵树。
    • 有序遍历 -以有序方式遍历树。
    • 后序遍历 -以后序方式遍历树。
    在本章中,我们将学习创建(插入)树结构并在树中搜索数据项。在下一章中,我们将学习树遍历方法。
  • 插入操作

    第一次插入将创建树。之后,无论何时要插入元素,都首先要找到其正确位置。从根节点开始搜索,然后如果数据小于键值,则在左侧子树中搜索空位置并插入数据。否则,在右侧子树中搜索空白位置并插入数据。
    算法:
    
    If root is NULL 
       then create root node
    return
    
    If root exists then
       compare the data with node.data
       
       while until insertion position is located
    
          If data is greater than node.data
             goto right subtree
          else
             goto left subtree
    
       endwhile 
       
       insert data
      
    end If      
    
    例子:
    
    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, create root node
       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;
                }
             }
          }            
       }
    }
    
  • 搜索操作

    每当要搜索元素时,都从根节点开始搜索,然后,如果数据小于键值,则在左侧子树中搜索该元素。否则,在右子树中搜索该元素。每个节点遵循相同的算法。
    算法:
    
    If root.data is equal to search.data
       return root
    else
       while data not found
    
          If data is greater than node.data
             goto right subtree
          else
             goto left subtree
             
          If data found
             return node
       endwhile 
       
       return data not found
       
    end if      
    
    例子:
    
    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;
       }  
    }