二叉排序树(BST)

二叉排序树

二叉排序树的定义

  • 若左子树非空，则左子树上所有结点的值均小于根结点的值。
  • 若右子树非空，则右子树上所有结点的值均大于根结点的值
  • 左、右子树也分别是一颗二叉排序树。

二叉排序树的查找

二叉排序树中查找某关键字时，查找过程类似于次优二叉树，在二叉排序树不为空树的前提下，首先将被查找值同树的根结点进行比较，会有 3 种不同的结果：

  • 如果相等，查找成功；
  • 如果比较结果为根结点的关键字值较大，则说明该关键字可能存在其左子树中；
  • 如果比较结果为根结点的关键字值较小，则说明该关键字可能存在其右子树中；
  • 实现函数为：（运用递归的方法）
    1
    2
    3
    4
    5
    6
    7
    BSTNode *BST_Search(BSTree T,int key){
        while(T != NULL && key != T->key){  // 若树空或等于根结点值，则结束循环
            if(key < T->key) T = T->lchild; // 小于，则在左子树上查找
            else T = T->rchild;             // 大于，则在右子树上查找
        }
        return T;
    }

二叉排序树中插入关键字

  • 二叉排序树作为一种动态树表，其特点是树的结构通常不是一次生成的，而是在查找过程中,当树中不存在关键字值等于给定值的结点时再进行插入的。
  • 插入结点的过程如下：若原二叉排序树为空，则直接插入；否则，若关键字k小于根结点值,则插入到左子树，若关键字k大于根结点值，则插入到右子树。插入的结点一定是一个新添加的叶结点，且是查找失败时的查找路径上访问的最后一个结点的左孩子或右孩子。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    // 在二叉排序树中插入关键字为 k 的新结点(递归实现)
    int BST_Insert(BSTree *T,int k){
        if((*T) == NULL){                                   // 原树为空，新插入的结点为根节点
            (*T )= (BSTree) malloc(sizeof (BSTNode));
            (*T)->key = k;
            (*T)->lchild = (*T)->rchild = NULL;
            return 1;                                       //返回1，插入成功
        }
        else if(k == (*T)->key)                             //树中存在相同关键字的结点，插入失败
            return 0;
        else if(k < (*T)->key)                              // 插入到T的左子树
            return BST_Insert(&((*T)->lchild),k);
        else                                                // 插入到T的右子树
            return BST_Insert(&((*T)->rchild),k);
    }

二叉排序树的构造

1
2
3
4
5
6
7
8
9
// 二叉排序树的构造
void Creat_BST(BSTree *T,int str[],int n){
    *T = NULL;                              //初始时T为空树
    int i = 0;
    while(i < n){                           //依次将每个关键字插入到二叉排序树中
        BST_Insert(T,str[i]);
        i++;
    }
}

二叉树排序树的删除

  • 若被删除的结点z是叶结点，则直接删除，不会破坏二叉排序树的性质。
  • 若结点只有一颗左子树或右子树，则让z的子树称为z的父结点的子树，替代z的位置。
  • 若结点z有左、右子树，有两种方法
    • 令z的直接后继代替z，然后从二叉排序树中删去这个直接后继。z的直接后继–>z的右子树中最左下结点(该结点一定没有左子树)
    • 令z的直接前驱代替z，然后从二叉排序树中删去这个直接前驱。z的直接前驱–>z的左子树中最右下结点(该结点一定没有右子树)
      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
      27
      28
      29
      30
      31
      32
      33
      34
      35
      // 二叉排序树的删除
      BSTree Delete_BST(BSTree *T,int data) {
          if ((*T) == NULL) {
              printf("要删除的元素不存在！\n");
              return NULL;
          } else if ((*T)->key == data) {
              if ((*T)->lchild == NULL && (*T)->rchild == NULL) {
                  free(*T);
                  *T = NULL;
              } else if ((*T)->lchild == NULL) {
                  BSTree temp = *T;
                  (*T) = (*T)->rchild;
                  free(temp);
              } else if ((*T)->rchild == NULL) {
                  BSTree temp = (*T);
                  (*T) = (*T)->lchild;
                  free(temp);
              } else {
                  BSTree pre = (*T)->lchild;
                  while (pre->rchild != NULL) {
                      pre = pre->rchild;
                  }
                  (*T)->key = pre->key;
                  (*T)->lchild = Delete_BST(&((*T)->lchild),pre->key);

              }

          }
          else if((*T)->key < data){
              (*T)->rchild = Delete_BST(&((*T)->rchild),data);
          }else{
              (*T)->lchild = Delete_BST(&((*T)->lchild),data);
          }
          return (*T);
      }

查找效率分析



总结

完整代码

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <stdio.h>
#include <stdlib.h>

typedef struct BSTNode{
    int key;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

// 在二叉排序树中查找值为 key 的结点
BSTNode *BST_Search(BSTree T,int key){
    while(T != NULL && key != T->key){  // 若树空或等于根结点值，则结束循环
        if(key < T->key) T = T->lchild; // 小于，则在左子树上查找
        else T = T->rchild;             // 大于，则在右子树上查找
    }
    return T;
}

// 在二叉排序树中插入关键字为 k 的新结点(递归实现)
int BST_Insert(BSTree *T,int k){
    if((*T) == NULL){                                   // 原树为空，新插入的结点为根节点
        (*T )= (BSTree) malloc(sizeof (BSTNode));
        (*T)->key = k;
        (*T)->lchild = (*T)->rchild = NULL;
        return 1;                                       //返回1，插入成功
    }
    else if(k == (*T)->key)                             //树中存在相同关键字的结点，插入失败
        return 0;
    else if(k < (*T)->key)                              // 插入到T的左子树
        return BST_Insert(&((*T)->lchild),k);
    else                                                // 插入到T的右子树
        return BST_Insert(&((*T)->rchild),k);
}

// 二叉排序树的删除
BSTree Delete_BST(BSTree *T,int data) {
    if ((*T) == NULL) {
        printf("要删除的元素不存在！\n");
        return NULL;
    } else if ((*T)->key == data) {
        if ((*T)->lchild == NULL && (*T)->rchild == NULL) {
            free(*T);
            *T = NULL;
        } else if ((*T)->lchild == NULL) {
            BSTree temp = *T;
            (*T) = (*T)->rchild;
            free(temp);
        } else if ((*T)->rchild == NULL) {
            BSTree temp = (*T);
            (*T) = (*T)->lchild;
            free(temp);
        } else {
            BSTree pre = (*T)->lchild;
            while (pre->rchild != NULL) {
                pre = pre->rchild;
            }
            (*T)->key = pre->key;
            (*T)->lchild = Delete_BST(&((*T)->lchild),pre->key);

        }

    }
    else if((*T)->key < data){
        (*T)->rchild = Delete_BST(&((*T)->rchild),data);
    }else{
        (*T)->lchild = Delete_BST(&((*T)->lchild),data);
    }
    return (*T);
}

// 二叉排序树的构造
void Creat_BST(BSTree *T,int str[],int n){
    *T = NULL;                              //初始时T为空树
    int i = 0;
    while(i < n){                           //依次将每个关键字插入到二叉排序树中
        BST_Insert(T,str[i]);
        i++;
    }
}

// 二叉排序树的中序遍历
void Display_BST(BSTree T){
    if(T == NULL) {
        return;
    }
    Display_BST(T->lchild);
    printf("%d ",T->key);
    Display_BST(T->rchild);
}

int main(){
    int n,key;
    printf("请输入要排序的个数:\n");
    scanf("%d",&n);
    int a[n];
    printf("请输入各元素的值:\n");
    for(int i = 0;i < n;i ++)
        scanf("%d",&a[i]);
    BSTree T;
    Creat_BST(&T,a,n);
    printf("中序遍历的结果如下:\n");
    Display_BST(T);
    printf("\n");
    int m;
    printf("请输入要删除数的个数:\n");
    scanf("%d",&m);
    for(int i = 0;i < m;i ++){
        printf("请输入要删除的元素的值:\n");
        scanf("%d",&key);
        Delete_BST(&T,key);
        printf("中序遍历的结果如下:\n");
        Display_BST(T);
    }
    return 0;
}
数据结构 > 第七章 > 树形查找
二叉排序树(BST)
https://lzyjx.github.io.git/2023/05/18/二叉排序树-BST/
作者
六只羊
发布于
2023年5月18日
许可协议