上一节:
下一节:

  数据结构&算法 树

  • 树

    树表示通过边连接的节点。我们将专门讨论二叉树或二叉搜索树。二叉树是用于数据存储目的的特殊数据结构。二叉树有一个特殊条件，即每个节点最多可以有两个孩子。二叉树既有序数组又有链表的好处，因为搜索与排序数组一样快，插入或删除操作也与链表一样快。
    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;
   }  
}
上一节:
下一节: