/**/

二分搜索树

首页 / 结构和算法入门教程 / 二分搜索树

二进制搜索树(BST)是一棵树,其中所有节点都遵循下述属性-

因此,BST将其所有子树分为两个部分:左子树和右子树,可以定义为-

left_subtree (keys)    node (key)    right_subtree (keys)

BST是以保持BST属性的方式排列的节点的集合,每个节点都有一个键和一个关联的值,在搜索时,将所需的键与BST中的键进行比较,如果找到,则会检索关联的值。

以下是BST的图形表示-

Binary Search Tree

我们观察到,根节点键(27)在左子树上具有所有值较低的键,而在右子树上具有较高值的​​键。

基本操作

以下是树的基本操作-

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

  • 插入           -   在树中插入一个元素。

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

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

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

Node 节点

定义一个包含一些数据的节点,并引用其左子节点和右子节点。

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

搜索操作

每当要搜索元素时,都从根节点开始搜索。然后,如果数据小于键值,则在左侧子树中搜索元素。否则在右子树中搜索该元素。

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

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

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

猜你喜欢

TensorFlow快速入门与实战 -〔彭靖田〕

苏杰的产品创新课 -〔苏杰〕

实用密码学 -〔范学雷〕

陶辉的网络协议集训班02期 -〔陶辉〕

进一步优化ISING模型

在 Svelte 中调用函数 onclick

比较两个数组的值并相应地创建对象

将值映射到项目数组以填充缺失的对象属性?

我如何在 Kotlin 中使用具有 .to 方法的 Java 库,因为它假定我的意思是使用中缀运算符来创建一对

如何使用 WSO2 Dataservice 从数据库中读取 Big Data ?

视频教程

数据结构和算法 - 47_线性表_链表_单向链表2 更多视频教程 »