树数据结构

树数据结构 首页 / 结构和算法入门教程 / 树数据结构

树表示通过边连接的节点,我们将专门讨论二叉树或二叉搜索树。

二叉树是用于数据存储目的的特殊数据结构,二叉树有一个特殊条件,即每个节点最多可以有两个孩子,二叉树既有序数组又有链表的好处,因为搜索与排序数组一样快,插入或删除操作也与链表一样快。

Binary Tree


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

  • Path           -   路径是指沿树边缘的节点序列。

  • Root           -   树顶部的节点称为根,每棵树只有一个根,并且有一个从根节点到任何节点的路径。

    链接:https://www.learnfk.comhttps://www.learnfk.com/data-structures-algorithms/tree-data-structure.html

    来源:LearnFk无涯教程网

  • Parent        -   除根节点外,任何节点的上边缘都指向称为父级的节点。

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

  • Leaf            -   没有任何子节点的节点称为叶子节点。

  • Subtree       -   子树表示节点的后代。

  • Visiting      -   访问是指在控件位于节点上时检查节点的值。

  • Traversing  -   遍历是指以特定顺序通过节点。

  • Levels         -   节点的级别表示节点的生成,如果根节点处于级别0,则其下一个子节点处于级别1,其子代处于级别2,依此类推。

  • Keys           -    key表示节点的值,基于该值将对节点执行搜索操作。

二分搜索树

二分搜索树表现出特殊的行为。节点的左子节点的值必须小于其父节点的值,并且节点的右子节点的值必须大于其父节点的值。

Binary Search Tree

我们将使用节点对象来实现树,并通过引用将它们连接起来。

树节点

编写树节点的代码与下面给出的代码相似。它有一个数据部分,并引用了它的左右子节点。

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

BST基本操作

可以对二分搜索树数据结构执行的基本操作如下:

  • 插入         -   在树中插入元素/创建树。

  • 搜索         -   搜索树中的元素。

  • 预定遍历 -   以预定顺序遍历一棵树。

  • 有序遍历 -   以有序方式遍历树。

  • 后序遍历 -   以后序方式遍历树。

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

插入操作

第一次插入将创建树,之后,无论何时要插入元素,都首先要找到其正确位置,从根节点开始搜索,然后如果数据小于键值,则在左侧子树中搜索空位置并插入数据。否则,在右侧子树中搜索空白位置并插入数据。

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

C实现二分搜索

#include <stdio.h>
#include <stdlib.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 pre_order_traversal(struct node* root) {
   if(root != NULL) {
      printf("%d ",root->data);
      pre_order_traversal(root->leftChild);
      pre_order_traversal(root->rightChild);
   }
}

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

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

int main() {
   int i;
   int array[7] = { 27, 14, 35, 10, 19, 31, 42 };

   for(i = 0; i < 7; i++)
      insert(array[i]);

   i = 31;
   struct node * temp = search(i);

   if(temp != NULL) {
      printf("[%d] Element found.", temp->data);
      printf("\n");
   }else {
      printf("[ x ] Element not found (%d).\n", i);
   }

   i = 15;
   temp = search(i);

   if(temp != NULL) {
      printf("[%d] Element found.", temp->data);
      printf("\n");
   }else {
      printf("[ x ] Element not found (%d).\n", i);
   }            

   printf("\nPreorder traversal: ");
   pre_order_traversal(root);

   printf("\nInorder traversal: ");
   inorder_traversal(root);

   printf("\nPost order traversal: ");
   post_order_traversal(root);       

   return 0;
}
Visiting elements: 27 35 [31] Element found.
Visiting elements: 27 14 19 [ x ] Element not found (15).

Preorder traversal: 27 14 10 19 35 31 42 
Inorder traversal: 10 14 19 27 31 35 42 
Post order traversal: 10 19 14 31 42 35 27

祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)

技术教程推荐

深入浅出区块链 -〔陈浩〕

大规模数据处理实战 -〔蔡元楠〕

Swift核心技术与实战 -〔张杰〕

ZooKeeper实战与源码剖析 -〔么敬国〕

性能工程高手课 -〔庄振运〕

罗剑锋的C++实战笔记 -〔罗剑锋〕

互联网人的英语私教课 -〔陈亦峰〕

Redis核心技术与实战 -〔蒋德钧〕

互联网人的数字化企业生存指南 -〔沈欣〕

好记忆不如烂笔头。留下您的足迹吧 :)