/**/

树数据结构

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

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

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

Binary Tree


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

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

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

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

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

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

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

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

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

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

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

二分搜索树

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

Binary Search Tree

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

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

来源:LearnFk无涯教程网

树节点

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

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

这一章《树数据结构》你学到了什么?在下面做个笔记吧!做站不易,你的分享是对我们最大的支持,感谢!😊

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

猜你喜欢

硅谷产品实战36讲 -〔曲晓音〕

深入浅出计算机组成原理 -〔徐文浩〕

体验设计案例课 -〔炒炒〕

程序员的个人财富课 -〔王喆〕

在 Python 中使用 Streamlit 的待办事项应用程序可能存在什么问题?

如何在 Flutter 中遍历嵌套的动态 JSON 文件

Typescript 具有对象的属性类型

文本 node 不能作为 [ReactJS] 的子 node 出现;警告:列表中的每个子元素都应该有一个独特的“关键”props

我不断收到 name 'message' not defined in python 即使我在函数中将其设为全局变量并调用它

在 setsockopt 函数中使用哪个 sock_fd

视频教程

数据结构和算法 - 124_树_红黑树_结点类设计 更多视频教程 »