数据结构和算法 - 树

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

二叉树是一种用于数据存储目的的特殊数据结构.二叉树具有特殊条件，即每个节点最多可以有两个子节点.二叉树具有有序数组和链表的优点，因为搜索与排序数组一样快，插入或删除操作与链表一样快.

重要条款

以下是关于树的重要术语.

• 路径 : 路径是指沿着树的边缘的节点序列.

• Root : 树顶部的节点称为root.每个树只有一个根，从根节点到任何节点只有一条路径.

• 父 : 除根节点外的任何节点都有一条边向上到一个名为parent的节点.

• Child : 通过其边缘向下连接的给定节点下方的节点称为其子节点.

• Leaf : 没有任何子节点的节点称为叶节点.

• 子树 : 子树表示节点的后代.

• 访问 : 访问是指当控制在节点上时检查节点的值.

• 遍历 : 遍历意味着按特定顺序遍历节点.

• 级别 : 节点的级别表示节点的生成.如果根节点处于级别0，则其下一个子节点处于级别1，其孙级处于级别2，依此类推.

• 键 :  Key表示节点的值，基于该节点对节点执行搜索操作.

二进制搜索树表示

二进制搜索树表现出特殊行为.节点的左子节点的值必须小于其父节点的值，并且节点的右子节点的值必须大于其父节点值.

我们将使用节点对象实现树并通过引用连接它们.

树节点

编写树节点的代码与下面给出的代码类似.它有一个数据部分和对其左右子节点的引用.

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

在树中，所有节点共享公共构造.

BST基本操作

可以在二叉搜索树数据结构上执行的基本操作是以下 :

• 插入 : 在树中插入元素/创建树.

• 搜索 : 搜索树中的元素.

• Preorder Traversal : 以预购方式遍历树.

• Inorder Traversal : 按顺序遍历树.

• Postorder Traversal : 以后序方式遍历树.

我们将学习创建(插入)树结构并搜索数据项本章中的一棵树.我们将在下一章中学习树遍历方法.

插入操作

第一次插入会创建树.之后，每当要插入元素时，首先找到其正确的位置.从根节点开始搜索，然后如果数据小于键值，则在左子树中搜索空位置并插入数据.否则，搜索右子树中的空位置并插入数据.

算法

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

实施

执行insert函数应该看起来像这样 :

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