526互联

二叉搜索树（BST，binary search tree）

发布时间 2023-08-16 17:02:22作者: 难者亦易矣

　　对于静态查找可以用二分查找，将查找时间复杂度降到 log2 n 。其中，虽然数据存储在线性的结构里，但我们事先对数据进行了处理，在查找的顺序过程中运用到判定树这样的结构，将线性上的查找过程转变为了在类似树上面的查找过程，其查找的效率就是树的高度。但如果查找的集合不仅有查找还有删除新增的需求，而树具有良好的动态性，为什么不直接将数据放在树里呢，我们所称的二叉搜索树可以很好的解决该问题。

　　

　　一棵不为空的二叉搜索树具有以下性质：

       1.非空的左子树的所有键值小于根的键值

　　2.非空的右子树的所有键值大于根的键值

　　3.左右子树都是二叉搜索树

一、树的结构

1 struct Node{
2     int data;
3     Node* left;
4     Node* right;
5 };
   Node* Null; //自定义空指针（个人习惯）

 二、利用非递归函数进行查找

 1 Node* Find(int x,Node* u)
 2 {
 3     while( u!=Null )
 4     {
 5         if( u->data > x ) u=u->right;
 6         else if( u->data < x ) u=u->left;
 7         else return u;
 8     }
 9     return Null;
10 }

三、查找最大、最小值

1 Node* FindMax( Node* u )   
2 {
3     //一直到最右边就是最大值
4     while( u!=Null && u->right!=Null )
5     {
6         u=u->right;
7     }
8     return u;
9 }
 1 Node* FindMin( Node* u ) 
 2 {
 3     //一直到最左边就是最小值
 4     while( u!=Null && u->left!=Null )
 5     {
 6         u=u->left;
 7     }
 8     return u;
 9     
10 }

四、插入

 1 Node* Insert( int x,Node* u )
 2 {
 3     if( u==Null )
 4     {
 5         u=(Node*)malloc(sizeof(struct Node)); //c++记得强制类型转换
 6         u->data=x;
 7         u->left=u->right=Null;
 8     }
 9     else
10     {
11         if( x > u->data ) u->right=Insert( x,u->right );
12         else if( x < u->data ) u->left=Insert( x,u->left );
13     }
14     return u;
15 }

五、删除

 1 Node* Delete( int x,Node* u )
 2 {
 3     if( x > u->data ) u->right=Delete( x,u->right );
 4     else if( x < u->data ) u->left=Delete( x,u->left );
 5     else
 6     {
 7         if( u->left!=Null && u->right!=Null )
 8         {
 9             Node* temp=FindMin( u->right );
10             u->right=Delete( temp->data,u->right );
11             u->data=temp->data;
12         }else
13         {
14             Node* temp=u;
15             if( u->left!=Null ) u=u->left;
16             else u=u->right;
17             free(temp);
18         }
19 
20     }
21     return u;
22 }