二叉搜索树

二叉搜索树概念

二叉搜索树（BST，Binary Search Tree），也称二叉排序树或二叉查找树。

二叉搜索树：一棵二叉树，可以为空；如果不为空，满足以下性质：

1. 非空左子树的所有键值小于其根结点的键值。
2. 非空右子树的所有键值大于其根结点的键值。
3. 左、右子树都是二叉搜索树。

对于二叉搜索树的抽象数据类型如下：

二叉搜索树的查找

查找某个元素

• 查找从根结点开始，如果树为空，返回NULL
• 若搜索树非空，则根结点关键字和X进行比较，并进行不同处理：
   若X小于根结点键值，只需在左子树中继续搜索；
   如果X大于根结点的键值，在右子树中进行继续搜索；
   若两者比较结果是相等，搜索完成，返回指向此结点的指针。

所谓尾递归，即在return时发生的递归，尾递归一般可以改写成循环：

对于二叉搜索树的查找操作，其查找的效率依赖于树的高度。如果所有的节点都只有左儿子而没有右儿子，此时形成了一条链，查找的效率就达不到logn，从这里也可以理解，只有树越平衡（左子树和右子树节点差不多），查找的效率才会越高，越接近logn。
该部分可以参考二分查找判定树https://blog.csdn.net/qq_38048756/article/details/118874713。

查找最大和最小元素

查找最大元素以及最小元素实现时都有两种实现方式，一种是递归，一种是循环。

二叉搜索树的插入结点

首先与当前节点比较，若比当前结点值大，往右子树递归，此时要求递归函数返回插入后的根节点的位置，然后把这个位置挂在当前节点上的右指针上就可以了；若比当前结点值小，往左子树递归，此时要求递归函数返回插入后的根节点的位置，然后把这个位置挂在当前节点上的左指针上就可以了。

二叉搜索树的删除结点

二叉搜索树的删除要考虑三种情况：

• 要删除的是叶结点：直接删除，并再修改其父结点指针（置为NULL）
• 要删除的结点只有一个孩子结点：将其父节点的指针指向要删除结点的孩子结点
• 要删除的结点有左、右两棵子树：用另一结点替代被删除结点：右子树的最小元素或者左子树的最大元素，然后再将右子树的最小元素或者左子树的最大元素删除。

第一种情况：

第二种情况：

第三种情况：

整体代码

如下为全部实现的代码：

#include<stdio.h>
#include<stdlib.h>

typedef int ElementType;
typedef struct TreeNode *BinTree;
struct TreeNode{
    
	ElementType Data;
	BinTree Left;
	BinTree Right;
};
BinTree create(BinTree BST);

void preorder(BinTree BST);
void inorder(BinTree BST);

BinTree Find(ElementType x, BinTree BST);
BinTree Find2(ElementType x, BinTree BST);
BinTree FindMin(BinTree BST);
BinTree FindMax(BinTree BST);

BinTree Insert(ElementType x, BinTree BST);
BinTree Delete(ElementType x, BinTree BST);

int main()
{
    
     BinTree BST = NULL;
     BinTree postion = NULL;
     BST = create(BST);
     postion = Find(33, BST);
     printf("%d\n", postion->Data);
     inorder(BST);
     printf("\n");
     postion = FindMax(BST);
     printf("最大值%d\n", postion->Data);
     postion = FindMin(BST);
     printf("最小值%d\n", postion->Data);

     Insert(35, BST);
     inorder(BST);

     printf("\n");
     Delete(41, BST);
     inorder(BST);



     return 0;
}

void preorder(BinTree BST)
{
    
     if(BST)
     {
    
          printf("%d ", BST->Data);
          preorder(BST->Left);
          preorder(BST->Right);
     }
}
void inorder(BinTree BST)
{
    
     if(BST)
     {
    
          inorder(BST->Left);
          inorder(BST->Right);
          printf("%d ", BST->Data);

     }
}
BinTree Insert(ElementType x, BinTree BST)
{
    
     //树为空，生成并返回一个结点的二叉搜素树
     if(!BST)
     {
    
          BST = (BinTree)malloc(sizeof(struct TreeNode));
          BST->Data = x;
          BST->Left = NULL;
          BST->Right = NULL;
     }
     else{
      //寻找插入元素的位置
          if(x < BST->Data)
               BST->Left = Insert(x, BST->Left);  //递归插入左子树
          else if(x > BST->Data)
               BST->Right = Insert(x, BST->Right);  //递归插入右子树
          //else x这个值已经存在，什么都不做
     }
     return BST;
}
BinTree Delete(ElementType x, BinTree BST)
{
    
     BinTree tmp;
     if(!BST) printf("要删除的元素没找到");
     else if (x < BST->Data)
          BST->Left = Delete(x, BST->Left);
     else if (x > BST->Data)
          BST->Right = Delete(x, BST->Right);
     else{
    
               if(BST->Left && BST->Right)
               {
    
                    tmp = FindMin(BST->Right);
                    BST->Data = tmp->Data;
                    BST->Right = Delete(BST->Data, BST->Right);
               }
               else{
    
                    tmp = BST;
                    if(!BST->Left)
                         BST = BST->Right;
                    else if(!BST->Right)
                         BST = BST->Left;
                    free(tmp);
               }
     }
     return BST;
}

BinTree create(BinTree BST)
{
    
     BST = Insert(30, BST);
     BST = Insert(15, BST);
     BST = Insert(41, BST);
     BST = Insert(33, BST);
     BST = Insert(50, BST);
     return BST;

}

BinTree Find(ElementType x, BinTree BST)
{
    
     if(!BST) return NULL;
     if(x > BST->Data)
          return Find(x, BST->Right);
     else if(x < BST->Data)
          return Find(x, BST->Left);
     else
          return BST;
}
BinTree Find2(ElementType x, BinTree BST)
{
    
     while(BST)
     {
    
          if(x > BST->Data)
               BST = BST->Right;
          else if(x < BST->Data)
               BST = BST->Left;
          else
               return BST;
     }
     return NULL;
}
BinTree FindMin(BinTree BST)
{
    
     /* // 递归求解 if(!BST) return NULL; //空的二叉搜索树，返回NULL else if(!BST->Left) return BST; //找到最左叶节点返回 else return FindMin(BST->Left); //沿左分支继续查找 */
     //迭代求解
     if(BST)
     {
    
          while(BST->Left)
               BST = BST->Left;
     }
     return BST;
}
BinTree FindMax(BinTree BST)
{
    

     // 递归求解
     if(!BST)
          return NULL;  //空的二叉搜索树，返回NULL
     else if(!BST->Right)
          return BST;  //找到最左叶节点返回
     else
          return FindMax(BST->Right);  //沿左分支继续查找
     /* //迭代求解 if(BST) { while(BST->Right) BST = BST->Right; } return BST; */
}

参考：浙大数据结构