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

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

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

二叉搜索树操作的一些重要函数

  • Position Find( ElementType X, BinTree BST )：从二叉搜索树BST 中查找元素X，返回其所在结点的地址；
  • Position FindMin( BinTree BST )：从二叉搜索树BST中查找并返回 最小元素所在结点的地址；
  • Position FindMax( BinTree BST ) ：从二叉搜索树BST中查找并返回 最大元素所在结点的地址。
  • BinTree Insert( ElementType X, BinTree BST ) ：
  • BinTree Delete( ElementType X, BinTree BST )：

二叉树的搜索

查找从根结点开始，如果树为空，返回NULL

若搜索树非空，则根结点关键字和X进行比较，并进行不同处理：

  • 若X小于根结点键值，只需在左子树中继续搜索；
  • 如果X大于根结点的键值，在右子树中进行继续搜索；
  • 若两者比较结果是相等，搜索完成，返回指向此结点的指针。

递归实现

1
2
3
4
5
6
7
8
9
10
Position  Find  ( ElementType  X , BinTree BST ){     // 递归查找

      if  ( !BST )   return NULL;   // 树空 查找失败
      if ( X < BST->Data)      // 小于父节点 在左子树中继续查找
            return Find ( X , BST->Left ) ;
      else if ( X > BST->Data)      // 大于父节点 在右子树中继续查找
            return Find ( X , BST->Right ) ;
      else  // 都不成立 则已经找到 返回找到结点的地址
            return BST;
}

由于递归实现的效率不高，所以我们可以将此种递归 ——“尾递归”转化为迭代函数

迭代实现

1
2
3
4
5
6
7
8
9
10
11
12
Position  Find ( ElementType  X , BinTree BST ){      // 非递归查找
    
      while ( BST ){
            if ( X < BST->Data )     // 小于父节点 在左子树中继续查找
                  BST = BST->Left;
            else if ( X > BST->Data )     // 大于父节点 在右子树中继续查找
                  BST = BST->Right;
            else  // X == BST->Data
                  return BST  // 都不成立 则已经找到 返回找到结点的地址
      }
      return NULL ;
}

查找最大最小元素

根据搜索二叉树特点，我们可以知道：

  • 最大元素一定是在树的最右分枝的端结点上
  • 最小元素一定是在树的最左分枝的端结点上

而且，由普通查找算法可知，查找最大和最小元素也有两种方法

查找的最大和最小只是向左向右有所不同，所以在此仅仅写上查找最大值的两种实现函数

递归函数

1
2
3
4
5
6
7
8
osition  FindMax ( BinTree BST ){
      if ( !BST )
            return NULL ;     // 空树 返回NULL
      else if ( !BST->Right )
            return BST;       // 右子树为空 直接返回自身
      else
            retuen FindMax (BST->Right)   // 右子树不空 对右子树进行递归
}

迭代函数

1
2
3
4
5
6
7
Position  FindMax ( BinTree BST ){      
    if ( BST )            
        while ( BST->Right)     
            BST = BST->Right ;            
    		// 树不空 则直接进行循环查找 直到最右叶节点      
    return BST;
}

二叉搜索树的插入

插入的重点在于找到插入的位置，而找位置的方法也就是Find方法，找到之后将元素插入即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
BinTree  Insert  ( ElementType X , BinTree BST ){
      if (!BST){  // 空树 生成并返回一个结点的二叉搜索树
            BST = malloc(sizeof(struct TreeNode));
            BST->Data = X;
            BST->Left = 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 );
            
      return BST ;
}

注：

第一个 if 语句的两个作用：

  • 刚开始判断是否为空树（第一次传入的树），如果为空树，则创建树
  • 找到插入点后进行插入

二叉搜索树的删除

二叉搜索树的删除主要分为三种情况：

  • 删除叶节点：直接删除，之后将父节点指针置为NULL

  • 删除的结点只有一个子节点：将其父结点的指针指向要删除的结点的子结点

  • 删除的结点有两个完整的子节点，也就是有左右两棵子树：

    • 可以采用另一结点替代被删除结点：左子树最大的元素或者右子树最小的元素，因为只有这样操作，才能在结点删除之后，仍然是一棵完整的二叉搜索树

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
BinTree Delete ( ElementType X , BinTree BST ){
      Position Tmp;
      if ( !BST )       printf ( "要删除的元素未找到" );
      else if ( X < BST->Data )     // 左子树递归删除
            BST->Left = Delet( X , BST->Left) ;
      else if ( X > BST->Data )     // 右子树递归删除
            BST->Right = Delet( X , BST->Right );
      else        // 找到需要删除的结点
            if ( BST->Left && BST->Right ){     // 删除节点的左右结点都存在
                  Tmp = FindMin( BST->Right )   // 寻找右子树中最小值 赋给Tmp
                  BST->Data = Tmp->Data;        
                  // 找到后赋值给需要删除的结点 将其覆盖
                  BST->Right = Delet(BST->Data , BST->Right) ;
                  // 在右子树中递归删除 覆盖了原结点的结点
            } else {         // 左右子树只存在一个或均不存在
                  Tmp = BST;
                  if ( !BST->Left )       // 左子树不存在
                        BST = BST->Right ;      
                        // 将其右子树接到要删除结点的上一个结点
                  else if ( !BST->Right )       // 右子树不存在
                        BST = BST->Left;
                        // 将其右子树接到要删除结点的上一个结点
                  free(Tmp);  // 释放Tmp
            }
            return BST ;
}