二叉排序树又称二叉搜索树，若它的左子树不为空，则左子树上所有结点的值都小于根节点的值。

若它的右子树不为空，则右子树上所有结点的值都大于根结点的值。

二叉排序树的左右子树也分别为二叉排序树。

如何存储二叉排序树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define eletype int

// 定义最大结点个数 
const int max_nodes = 100;

// 结点结构体定义 
struct Node {
    eletype data; // 结点数据（eletype表示数据类型，此时为int） 
    int *left, *right; // 左右子结点索引 
};

// 全局变量 
Node tree[max_nodes]; // 树的存储数组 
int root = 0, size = 1; // root是根结点的下标（0时是空树），size是下一个可用的存储空间的下标，size - 1是大小

二叉排序树的操作

查找

从根节点开始查找，如果大于根结点则向右查找，小于根结点则向左查找。 我们可以看下面的这个动画演示，在这个动画中要查找的是63。

在二又排序树的查找过程中，由于需要反复查询左右子树，可以考虑使用递归来实现查找操作。查找的递归解题思想如下:

  1. 如果树非空，则将目标值与当前结点的值进行比较。

  2. 如果目标值小于当前结点的值，则递归遍历左子树。

  3. 如果目标值大于当前结点的值，则递归遍历右子树。

  4. 如果目标值等于当前结点的值，则查找成功，返回该结点的索引值

1
2
3
4
5
6
7
8
9
int searchtree(int index, eletype value) { // index为当前结点，value为查找的值 
    if(index == 0) // 如果当前结点，返回0表示 
        return 0;
    if(tree[index].data == value) // 如果查找到了，返回 
        return index;
    if(value < tree[index].data) // 如果value小于当前位 
        return searchtree(tree[index].left, value); // 向左遍历 
    return searchtree(tree[index].right, value); // 否则向右遍历 
}

插入

按照序列 {50, 25, 75, 89, 63, 37, 12} 建立二叉排序树（BST）。我们可以看下面的这个动画演示。

插入操作是向二又排序树中添加新结点的过程。从根结点开始，根据节点值与当前节点的大小关系逐级向下比较，插入操作的基木思路是:

  1. 如果待插入结点的值小于当前结点的值，则继续在当前结点的左子树中查找。

  2. 如果待插入结点的值大于当前结点的值，则继续在当前结点的右子树中查找。

  3. 找到一个空结点，将待插入节点插入到该空结点的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
int insert_tree(int index, eletype value) {
    if(index == 0) { // 如果当前位置为空，代表这是插入进来的数据的位置 
        tree[size].data = value; // data赋值 
        // 左右子结点默认为空 
        tree[size].left = nullptr; 
        tree[size].right = nullptr;
    }
    if(key < tree[index].data) // 如果插入的数据小于当前位 
        tree[index].left = insert_tree(tree[index].left, value); // 向左递归 
    else if(key > tree[index].data) // 如果插入的数据大于当前位 
        tree[index].right = insert_tree(tree[index].right, value); // 向右递归
    return index;
}

遍历

二又树的遍历有三种，即前序遍历、中序遍历、后续遍历。一般使用中序遍历二叉排序树，即左根右的顺序，遍历操作的基本思路是:

  1. 如果当前结点索引为0，直接返回（空结点）。

  2. 递归遍历当前结点的左子树

  3. 输出当前结点的值

  4. 递归遍历当前结点的右子树

1
2
3
4
5
6
7
8
void inorderTraversal(Node *index) {
    if (index == 0) {
        return;
    }
    inorderTraversal(index->left);
    cout << index->val << " ";
    inorderTraversal(index->right);
}

删除

二叉树的删除操作比遍历、查询和插入操作更为复杂。删除结点可以分为三种情况。

第一种情况：删除的结点 P 为叶子结点

如果 P 结点为叶子结点，那么其左右子树都为空，也就是说删除此结点并不会破坏整棵树的结构，直接删除结点 P 即可。

以数组 {50, 25, 75, 89, 63, 37, 12} 为例，要删除叶子结点 63 的叶子结点。我们可以看下面的动画演示。

第二种情况：删除的结点 P 只有左孩子 P1 或者右孩子 P2

用它的那棵唯一的子树直接顶替它原来的位置——不需要再去找什么前驱、后继，也用不着旋转、染色之类的花哨操作。具体步骤分两步：

  1. 把 P 的父结点 F 中指向 P 的那条指针（F.lchild 或 F.rchild）改成指向 P 的独苗孩子 C（C 可能是 P1 也可能是 P2）。

  2. 释放（或回收）P 结点本身。

就这么简单，时间复杂度 O(1)，树高不变，BST 性质也天然保持。以数组 {47, 18, 80, 13, 29, 79, 90, 95} 为例，要删除结点 90。我们可以看下面的动画演示。

第三种情况：删除的节点P的左右子树都不为空

当待删结点 P 的左右子树均非空时，“直接顶替”会立刻破坏 BST 序，所以必须挑一个“合法替身”来接盘。
合法替身只有两类：

  1. 左子树里的最大结点——即 P 的前驱（in-order predecessor）。

  2. 右子树里的最小结点——即 P 的后继（in-order successor）。

任选其一即可，下面以前驱法为例给出完整流程（后继法对称）。

前驱法（in-order predecessor）删除步骤
记 P 的左子树根为 L。

  1. 在 L 的右链上一直向右走，直到右指针为空的结点 Q；
    Q 就是 P 的直接前驱，且 Q 一定没有右子树（否则还能再往右）。

  2. 把 Q 的数据域复制到 P，完成“值替换”。

  3. 现在问题转化为“删除 Q”：
    – 若 Q 是 L 本身（说明 L 没有右子树），则把 P 的左指针指向 L 的左子树；
    – 否则 Q 是某个结点 R 的右孩子，把 R 的右指针指向 Q 的左子树（Q 最多只有左子树）。

  4. 释放 Q。

后继法（in-order successor）一句话总结
在右子树里一直往左走到头，把那个最小结点复制到 P，然后删除那个最小结点（它最多只有右子树），操作完全对称。

算法复杂度

  • 搜索前驱/后继：O(h)，h 为树高。

  • 复制与重新链接：O(1)。

  • 总时间复杂度：O(h)；对于平衡树即 O(log n)。

以序列 {47, 18, 80, 13, 29, 79, 95} 为例，删除结点 80。我们可以看下面的动画演示。

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
Node* deleteNode(Node* index, int value) {
    if (index == NULL) {
        cout << "未找到值为 " << value << " 的节点" << endl;
        return NULL;
    }
    if (value < index->val) {
        index->left = deleteNode(index->left, value);
    }
    else if (value > index->val) {
        index->right = deleteNode(index->right, value);
    }
    else {
        
        if (index->left == NULL) {
            Node* temp = index->right;
            delete index;
            cout << "成功删除节点: " << value << endl;
            return temp;
        }
        else if (index->right == NULL) {
            Node* temp = index->left;
            delete index;
            cout << "成功删除节点: " << value << endl;
            return temp;
        }
        
        Node* temp = findMin(index->right);
        
        index->val = temp->val;
        
        index->right = deleteNode(index->right, temp->val);
        
        cout << "成功删除节点: " << value << endl;
    }
    
    return index;
}

最后附上全部代码

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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};
TreeNode* createNode(int value) {
    TreeNode* newNode = new TreeNode;
    newNode->val = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
void insertNode(TreeNode* &root, int key) {
    if (root == NULL) {
        root = createNode(key);
        return;
    } 
    if (key < root->val) {
        insertNode(root->left, key);
    }
    else if (key > root->val) {
        insertNode(root->right, key);
    }
    else {
        cout << "值 " << key << " 已存在，不重复插入" << endl;
    }
}

bool searchNode(TreeNode* root, int key) {
    if (root == NULL) {
        return false;
    }  
    if (key == root->val) {
        return true;
    }
    else if (key < root->val) {
        return searchNode(root->left, key);
    }
    else {
        return searchNode(root->right, key);
    }
}
void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}
TreeNode* findMin(TreeNode* root) {
    if (root == NULL) {
        return NULL;
    }
    while (root->left != NULL) {
        root = root->left;
    }
    
    return root;
}
TreeNode* deleteNode(TreeNode* root, int key) {
    if (root == NULL) {
        cout << "未找到值为 " << key << " 的节点" << endl;
        return NULL;
    }
    if (key < root->val) {
        root->left = deleteNode(root->left, key);
    }
    else if (key > root->val) {
        root->right = deleteNode(root->right, key);
    }
    else {
        
        if (root->left == NULL) {
            TreeNode* temp = root->right;
            delete root;
            cout << "成功删除节点: " << key << endl;
            return temp;
        }
        else if (root->right == NULL) {
            TreeNode* temp = root->left;
            delete root;
            cout << "成功删除节点: " << key << endl;
            return temp;
        }
        
        TreeNode* temp = findMin(root->right);
        
        root->val = temp->val;
        
        root->right = deleteNode(root->right, temp->val);
        
        cout << "成功删除节点: " << key << endl;
    }
    
    return root;
}
void freeTree(TreeNode* &root) {
    if (root == NULL) {
        return;
    }  
    freeTree(root->left);
    freeTree(root->right);
    delete root;
    root = NULL;
}
int getHeight(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);
    if (leftHeight > rightHeight) {
        return leftHeight + 1;
    } else {
        return rightHeight + 1;
    }
}
int countNodes(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    
    int leftCount = countNodes(root->left);
    int rightCount = countNodes(root->right);
    
    return leftCount + rightCount + 1;
}

void displayTree(TreeNode* root, string prefix, bool isLeft) {
    if (root == NULL) {
        return;
    } 
    cout << prefix;
    cout << (isLeft ? "├──" : "└──" );
    cout << root->val << endl;
    
    if (root->left != NULL || root->right != NULL) {
        displayTree(root->left, prefix + (isLeft ? "│   " : "    "), true);
        displayTree(root->right, prefix + (isLeft ? "│   " : "    "), false);
    }
}

int main() {
    TreeNode* root = NULL;
    int choice, key;
    cout << "========== 二叉排序树操作系统 ==========" << endl;
    cout << "说明：二叉排序树（BST）具有以下性质：" << endl;
    cout << "1. 左子树所有节点值 < 根节点值" << endl;
    cout << "2. 右子树所有节点值 > 根节点值" << endl;
    cout << "3. 左右子树也都是BST" << endl << endl;
    while (true) {
        cout << "\n========== 操作菜单 ==========" << endl;
        cout << "1. 插入元素（支持批量插入）" << endl;
        cout << "2. 查找元素" << endl;
        cout << "3. 中序遍历（显示排序结果）" << endl;
        cout << "4. 删除节点" << endl;
        cout << "5. 显示树的高度" << endl;
        cout << "6. 显示节点总数" << endl;
        cout << "7. 显示树形结构" << endl;
        cout << "8. 清空整棵树" << endl;
        cout << "9. 退出程序" << endl;
        cout << "请输入选择 (1-9): ";
        
        cin >> choice;
        
        switch (choice) {
            case 1: {
                cout << "批量插入说明：输入多个数字，以空格分隔，最后输入-1结束" << endl;
                cout << "请输入要插入的元素（输入-1结束）: ";
                
                while (cin >> key) {
                    if (key == -1) {
                        break;
                    }
                    
                    insertNode(root, key);
                    cout << "? 元素 " << key << " 插入成功" << endl;
                }
                
                cin.clear();
                cin.ignore(1000, '\n');
                
                break;
            }
            
            case 2: {
                if (root == NULL) {
                    cout << "树为空，请先插入元素！" << endl;
                    break;
                }
                
                cout << "请输入要查找的元素: ";
                cin >> key;
                
                if (searchNode(root, key)) {
                    cout << "? 元素 " << key << " 存在于树中" << endl;
                } else {
                    cout << "? 元素 " << key << " 不存在于树中" << endl;
                }
                
                break;
            }
            
            case 3: {
                cout << "中序遍历结果（升序排列）: ";
                
                if (root == NULL) {
                    cout << "树为空！" << endl;
                } else {
                    inorderTraversal(root);
                    cout << endl;
                }
                
                break;
            }
            
            case 4: {
                if (root == NULL) {
                    cout << "树为空，无法删除！" << endl;
                    break;
                }
                
                cout << "当前树的中序遍历: ";
                inorderTraversal(root);
                cout << endl;
                
                cout << "请输入要删除的元素: ";
                cin >> key;
                
                root = deleteNode(root, key);
                
                break;
            }
            
            case 5: {
                int height = getHeight(root);
                cout << "树的高度: " << height << endl;
                
                break;
            }
            
            case 6: {
                int count = countNodes(root);
                cout << "节点总数: " << count << endl;
                
                break;
            }
            
            case 7: {
                if (root == NULL) {
                    cout << "树为空！" << endl;
                } else {
                    cout << "树的形状:" << endl;
                    displayTree(root, "", true);
                }
                
                break;
            }
            
            case 8: {
                if (root == NULL) {
                    cout << "树已为空！" << endl;
                } else {
                    freeTree(root);
                    cout << "? 树已清空" << endl;
                }
                
                break;
            }
            
            case 9: {
                cout << "\n正在退出程序..." << endl;
                
                if (root != NULL) {
                    freeTree(root);
                }
                
                cout << "感谢使用！" << endl;
                
                return 0;
            }
            
            default: {
                cout << "错误：请输入1-9之间的数字！" << endl;
                
                cin.clear();
                cin.ignore(1000, '\n');
                
                break;
            }
        }
    }
    
    return 0;
}