二叉搜索树（二叉排序树）_关键字集合 100 60 40 80构成的二叉排序树

参考：https://blog.csdn.net/qq_35644234/article/details/64516551

（这位大佬真的强啊，很喜欢他的风格）

二叉搜索树

4.1 二叉搜索树定义

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

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

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

二叉排序树通常采用二叉链表作为存储结构。中序遍历二叉排序树便可得到一个有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即是对无序序列进行排序的过程。

4.2 操作

4.2.1 查找操作

查找的效率决定于树的高度

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

查找最大和最小元素

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

递归实现 & 非递归实现

4.2.2 插入操作

分析：关键是要找到元素应该插入的位置，可以采用与查找类似的方法

4.2.3 删除操作

考虑三种情况：

• 要删除的是叶结点：直接删除，并再修改其父结点指针–置为NULL
• 要删除的结点只有一个孩子结点：将其父结点的指针指向要删除结点的孩子结点
• 要删除的结点有左、右两棵子树：用另一结点替代被删除结点
  1. 取右子树中的最小元素替代
  2. 取左子树中的最大元素替代

4.3 代码实现

#include <iostream>

using namespace std;

typedef int ElemType;

struct BiTreeNode {
    ElemType data;
    BiTreeNode* left;
    BiTreeNode* right;
};

// 查找二叉排序树 成功返回true，失败返回false
// 指针p返回查找到的结果指针
bool searchBST(BiTreeNode* T, ElemType key, BiTreeNode*& p)
{
    if (!T) {
        p = nullptr;
        return false;
    }

    // 遍历整个二叉树
    while (T) {
        p = T;
        if (key == T->data) {	// 相等说明找到了对应关键字
            return true;
        }
        else if (key > T->data) {	// 往右子树查找
            T = T->right;
        }
        else if (key < T->data) {
            T = T->left;		// 往左子树查找
        }
    }
    // 如果执行到了这里，说明并未找到
    return false;
}


// 创建二叉排序树（插入操作）
bool createBST(BiTreeNode*& T, ElemType key)
{
    BiTreeNode* p;
    // 未查到key的存在，则创建
    if (!searchBST(T, key, p)) {
        BiTreeNode* newNode = new BiTreeNode;
        newNode->data = key;
        newNode->left = newNode->right = nullptr;

        if (!p) {		// 说明当前二叉树为空
            T = newNode;
        }
        else if (p->data > key) {	// 新插入结点为结点的左子树
            p->left = newNode;
        }
        else {
            p->right = newNode;	// 新插入结点为右子树
        }
        return true;
    }
    // 说明这个关键字已经在二叉排序树中
    return false;
}


// 删除关键字结点的删除部分, T为指向被删除节点的父结点
bool deleteNode(BiTreeNode*& T)
{
    BiTreeNode* q;			
    if (!T->left) {			// 左子树为空，直接接右子树
        q = T;
        T = T->right;
        delete q;
    }
    else if (!T->right) {	// 右子树为空，直接接左子树
        q = T;
        T = T->left;
        delete q;
    }
    else {	// 左右子树都不为空，则找左子树最靠右结点或右子树最靠左结点
        q = T;
        BiTreeNode* del = T->left;
        while (del->right) {
            q = del;
            del = del->right;
        }

        // 经过上面的while循环，q已经是指向左子树最靠右的结点的父结点
        // s为指向左子树最靠右的结点
        T->data = del->data;	// 只更新数据部分
        // 下面比较绕，需要画图看看
        // 处理要删除的s指针指向的左子树
        if (q != T) {
            q->right = del->left;
        }
        else {
            q->left = del->left;
        }
        delete del;
    }
    return true;
}
// 删除关键字结点
bool deleteBST(BiTreeNode*& T, ElemType key)
{
    if (!T) {	// 数为空直接返回
        return false;
    }

    while (T) {
        if (T->data == key) {
            return deleteNode(T);
        }
        else if (T->data < key) {	// key大，走向右子树
            T = T->right;
        }
        else {	// key小，走向左子树
            T = T->left;
        }
    }
    // 关键字不存在
    return false;
}

// 销毁二叉排序树
void destroyBST(BiTreeNode* T)
{
    if (T) {
        destroyBST(T->left);
        destroyBST(T->right);
        delete 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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

4.4 查找分析

使用二叉排序树进行查找，最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和logn成正比，即：（O(log2(n))）。

最坏情况下，当先后插入的关键字有序时，构成的二叉排序树为一棵斜树，树的深度为n，其平均查找长度为(n + 1) / 2。也就是时间复杂度为O(n)，等同于顺序查找。

因此，如果希望对一个集合按二叉排序树查找，最好是要对排序树进行一些必要的优化，如下：

• 加权平衡树(WBT)
• AVL树 (平衡二叉树)
• 红黑树
• Treap(Tree+Heap)

这些均可以使查找树的高度为 ：O(log（n）)