数据结构：二叉排序树

什么是二叉排序树？

二叉排序树要么是空二叉树，要么具有如下特点：

• 二叉排序树中，如果其根结点有左子树，那么左子树上所有结点的值都小于根结点的值；
• 二叉排序树中，如果其根结点有右子树，那么右子树上所有结点的值都大小根结点的值；
• 二叉排序树的左右子树也要求都是二叉排序树；

如图所示，就是一个二叉排序树：

使用二叉排序树查找关键字

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

• 如果相等，查找成功；
• 如果比较结果为根结点的关键字值较大，则说明该关键字可能存在其左子树中；
• 如果比较结果为根结点的关键字值较小，则说明该关键字可能存在其右子树中；

实现函数为：（运用递归的方法）

BSTree SreachBST(BSTree T, int key){
		//如果递归过程中 T 为空，则查找结果，返回NULL；或者查找成功，返回指向该关键字的指针
    if ((!T) || (key == T->data)) return T;
    else if(key < T->data) return SreachBST(T->lchild, key);//递归遍历其左孩子
    else return SreachBST(T->rchild, key);//递归遍历其右孩子
}
1
2
3
4
5
6

二叉排序树中插入关键字

二叉排序树本身是动态查找表的一种表示形式，有时会在查找过程中插入或者删除表中元素，当因为查找失败而需要插入数据元素时，该数据元素的插入位置一定位于二叉排序树的叶子结点，并且一定是查找失败时访问的最后一个结点的左孩子或者右孩子。

例如，在图 1 的二叉排序树中做查找关键字 1 的操作，当查找到关键字 3 所在的叶子结点时，判断出表中没有该关键字，此时关键字 1 的插入位置为关键字 3 的左孩子。

所以，二叉排序树表示动态查找表做插入操作，只需要稍微更改一下上面的代码就可以实现，具体实现代码为：

void InserBST(BSTree &T, int key){
    if(!T){//如果递归过程中T为空，则初始化插入结点
        BSTNode *S = new BSTNode;
        S->data = key;
        S->lchild = NULL;
        S->rchild = NULL;
        T = S;
    }
    else if(key < T->data) InserBST(T->lchild, key);
    else if(key > T->data) InserBST(T->rchild, key);
    else if(key == T->data) {cout << "该关键字在已存在！！！";return;}
}
1
2
3
4
5
6
7
8
9
10
11
12

通过使用二叉排序树对动态查找表做查找和插入的操作，同时在中序遍历二叉排序树时，可以得到有关所有关键字的一个有序的序列。

例如，假设原二叉排序树为空树，在对动态查找表 {3，5，7，2，1} 做查找以及插入操作时，可以构建出一个含有表中所有关键字的二叉排序树，过程如图 2 所示:

图 2 二叉排序树插入过程

通过不断的查找和插入操作，最终构建的二叉排序树如图 2（5） 所示。当使用中序遍历算法遍历二叉排序树时，得到的序列为： 1 2 3 5 7 ，为有序序列。

一个无序序列可以通过构建一棵二叉排序树，从而变成一个有序序列。

二叉排序树中删除关键字

在查找过程中，如果在使用二叉排序树表示的动态查找表中删除某个数据元素时，需要在成功删除该结点的同时，依旧使这棵树为二叉排序树。

假设要删除的为结点 p ，则对于二叉排序树来说，需要根据结点 p 所在不同的位置作不同的操作，有以下 3 种可能：

1、结点 p 为叶子结点，此时只需要删除该结点，并修改其双亲结点的指针即可；

2、结点 p 只有左子树或者只有右子树，如果 p 是其双亲节点的左孩子，则直接将 p 节点的左子树或右子树作为其双亲节点的左子树；反之也是如此，如果 p 是其双亲节点的右孩子，则直接将 p 节点的左子树或右子树作为其双亲节点的右子树；

3、结点 p 左右子树都有，此时有两种处理方式：

1）令结点 p 的左子树为其双亲结点的左子树；结点 p 的右子树为其自身直接前驱结点的右子树，简单理解：因为p的左子树所有结点都小于p的右子树结点，所以只需将p的左子树重接在p的父结点的左子树上，然后将p的右子树整体接入p左子树的最右端s即可。如图 3 所示；

图 3 二叉排序树中删除结点（1）

2）用结点 p 的直接前驱（或直接后继）来代替结点 p ，同时在二叉排序树中对其直接前驱（或直接后继）做删除操作，简单理解：因为p的左子树的最右端s是p的左子树所有结点关键字中最大的，所以只需用其代替p，然后将s的左子树为其父结点的右子树即可。如图 4 为使用直接前驱代替结点 p ：

图 4 二叉排序树中删除结点（2）

图 4 中，在对左图进行中序遍历时，得到的结点 p 的直接前驱结点为结点 s，所以直接用结点 s 覆盖结点 p，由于结点 s 还有左孩子，根据第 2 条规则，直接将其变为双亲结点的右孩子。

具体实现代码：（可运行）

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

BSTree SreachBST(BSTree T, int key){
		//如果递归过程中 T 为空，则查找结果，返回NULL；或者查找成功，返回指向该关键字的指针
    if ((!T) || (key == T->data)) return T;
    else if(key < T->data) return SreachBST(T->lchild, key);//递归遍历其左孩子
    else return SreachBST(T->rchild, key);//递归遍历其右孩子
}
void InserBST(BSTree &T, int key){
    if(!T){//如果递归过程中T为空，则初始化插入结点
        BSTNode *S = new BSTNode;
        S->data = key;
        S->lchild = NULL;
        S->rchild = NULL;
        T = S;
    }
    else if(key < T->data) InserBST(T->lchild, key);
    else if(key > T->data) InserBST(T->rchild, key);
    else if(key == T->data) {cout << "该关键字在已存在！！！";return;}
}
void CreatBST(BSTree &T){
    T = NULL;
    int key;
    cin >> key;
    while(key != -1){//-1表示输入结束
        InserBST(T, key);
        cin >> key;
    }
}
void DeleteBST(BSTree &T, int key){
    BSTree p = T, f = NULL;
    while (p){//找到要删除的关键字
        if (p->data == key) break;
        f = p;//f为p的父节点
        if (p->data > key) p = p->lchild;
        else p = p->rchild;
    }
    if (!p) return; //若p为空，则表示未找到要删除的结点
    BSTree q = p;
    if ((p->lchild) && (p->rchild)){//被删除的结点左右子树均不为空
        BSTree s = p->lchild;
        while (s->rchild){//在p的左子树中找到其前驱结点，即最右下结点
            q = s;
            s = s->rchild;
        }
        p->data = s->data;
        if(q != p) q->rchild = s->lchild;//接入q的右子树
        else q->lchild = s->lchild;//接入q的左子树
        delete s;
        return;
    }
    else if (!p->rchild){//被删除结点p没有右子树，只需重接其左子树
        p = p->lchild;
    }
    else if (!p->lchild){//被删除结点p灭有左子树，只需重接其右子树
        p = p->rchild;
    }
    if (!f) T = p;//被删除的是更节电
    else if (q = f->lchild) f->lchild = p;//q在那边就将p重接到那边
    else f->rchild = p;
    delete q;
}
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

总结

使用二叉排序树在查找表中做查找操作的时间复杂度同建立的二叉树本身的结构有关。即使查找表中各数据元素完全相同，但是不同的排列顺序，构建出的二叉排序树大不相同。

例如：查找表 {45，24，53，12，37，93} 和表 {12，24，37，45，53，93} 各自构建的二叉排序树图下图所示：

图 5 不同构造的二叉排序树

使用二叉排序树实现动态查找操作的过程，实际上就是从二叉排序树的根结点到查找元素结点的过程，所以时间复杂度同被查找元素所在的树的深度（层次数）有关。

为了弥补二叉排序树构造时产生如图 5 右侧所示的影响算法效率的因素，需要对二叉排序树做“平衡化”处理，使其成为一棵平衡二叉树。 平衡二叉树是动态查找表的另一种实现方式