性质写在前面：
上一讲我们介绍了二叉树的代码实现以及其遍历方法，这一讲我们来看一看进阶版的二叉树 —— 二叉排序树（二叉搜索树）。第一次接触这一讲知识点的朋友一时反应不过来不用太焦虑，其实是非常正常的，看讲解以及代码的同时动手画一画或者实现以下会让你更容易理解~
二叉排序树它和普通的二叉树不同：
（1）如果根结点的左子树不为空，那么它左子树的所有结点的值都小于根结点。
（2）如果根结点的右子树不为空，那么它右子树的所有结点的值都大于根结点。
（3）根结点的左子树和右子树同样遵循上面两条性质。
根据性质我们可以知道，这颗排序二叉树的实现必然逃不了递归了，接下来我们来看看排序二叉树的代码是如何实现的。
假设我们要构建起下面这颗二叉排序树，要进行如何操作呢：
（1）构建根结点 8 。
（2）插入结点 2 ，可以发现比根结点小，故插入根结点的左子树。
（3）插入结点 9 ，可以发现比根结点大，故插入根结点的右子树。
（4）插入结点 11 ，可以发现比根结点右孩子的值还要大，所以就插入到根结点右孩子的右子树。
（5）插入结点 23 ，可以发现比之前的值都要大，所以直接插到最右边的子树。
（6）插入结点 1 ，可以发现比之前的值都要小，所以直接插入到最左子树。
（7）最后插入结点 4 ，可以发现比根结点的左孩子要大，并且其左孩子没有右子树，所以直接插入即可。
整个操作的思想就是递归的思想，不断判断要插入结点的值和当前结点的值是大还是小，然后进入对应分支。
struct tree_node {
int data;
tree_node *left_child; //左孩子
tree_node *right_child; //右孩子
};
tree_node *root = NULL; //根结点指针
tree_node *temp = NULL; //临时指针
//初始化根结点
void init_root(int key) {
root = new tree_node;
root->data = key;
root->left_child = root->right_child = NULL;
}
//插入孩子
void insert_child(int key) {
if (root == NULL) {
cout << "请先创建根节点" << endl;
return;
}
temp = root; //用临时指针从根结点开始寻找合适的插入位置
while (1) {
//如果插入的值比当前结点要小，进入判断
if (key < temp->data) {
//如果当前结点的左子树为空，则直接构建新结点进行插入
if (temp->left_child == NULL) {
tree_node *new_node = new tree_node;
new_node->data = key;
new_node->left_child = new_node->right_child = NULL; //将新结点的左指针和右指针都初始化为空
temp->left_child = new_node; //将当前结点的左指针指向新结点
break;
}
//如果其左子树不为空，则进入其左子树继续进行判断
else {
temp = temp->left_child;
}
}
//如果插入的值比当前节点要大，进入判断
else {
//如果当前结点的右子树为空，则直接构建新结点继续插入
if (temp->right_child == NULL) {
tree_node *new_node = new tree_node;
new_node->data = key;
new_node->left_child = new_node->right_child = NULL; 将新结点的左指针和右指针都初始化为空
temp->right_child = new_node; //将当前结点的右指针指向新结点
break;
}
//如果其右子树不为空，则进入其右子树继续进行判断
else {
temp = temp->right_child;
}
}
}
}
二叉排序树的查找操作
我们这里的查找操作就不想数组查找那样那么直接，需要从根结点开始往下遍历进行比较。那么如果我们想要查找上面这颗二叉树的结点 4 ，该如何进行查找呢：
（1）先从根结点开始查找。
（2）可以发现我们要查找的结点 4 要比根结点 8 要小，所以我们进入根结点的左子树进行查找。
（3）结点 4 比结点 2 的值要大，所以我们进入其右子树进行查找。
（4）结果发现，当前遍历到的结点就是我们要查找的值，直接返回即可。
二叉排序树的删除操作就要比插入操作更加繁琐一些，需要分情况进行讨论，第一次学习不要慌张，一时头脑混乱非常正常，静下心来反复思考就可以吸收啦~
我们可以将删除操作分为三种情况：
（1）删除结点是叶子结点
如果删除结点是根结点，那么直接delete根结点指针即可，因为此时树中只有一个结点了。否则，同样delete删除结点即可，因为
假如我们要删除上面那棵树的结点 23 ，我们只用找到其父结点，然后将其父结点指向删除结点的指针指向空即可。
（2）如果删除的结点只有一个孩子
如果删除结点只有左孩子，那么只需将删除结点的左孩子连接到其父结点即可；如果删除结点只有右孩子，那么只需将删除结点的右孩子连接到其父结点即可。
如果删除结点是根结点则需另外操作，将根结点指针指向它的孩子即可。
假如我们要删除结点 11 ，那只用将结点 11 的右孩子直接接到其父结点 9 即可。
（3）如果删除结点既有左孩子也有右孩子。
这里我们有两种方法去实现，根结点和树中间的结点操作都是一样的，第一种方法是找到删除结点左子树中值最大的那个结点，然后与删除结点的值替换，并删除该结点。实际操作时，我们要从删除结点的左孩子开始查找，因为删除结点的左子树中，值最大的无非就是其左孩子或在左孩子的右子树当中，这里我们就拿删除根结点进行举例：
第二种方法是找到删除结点右孩子中最小的那个，交换并删除。同样，实际操作中也是从删除结点的右孩子开始查找，删除结点右子树中最小值一定在其右孩子或右孩子的左子树当中。这两种方法都保证删除后的树中结点仍然满足二叉排序树的性质，即左孩子都比根结点小，右孩子都比根结点大：
接下来我们来看代码的操作，这里我们是以上面第一种方法来实现的。另外，我们在实现代码时，会将一些操作合并在一起，因为有些情况的实现方法是相同的，比如说在当删除结点是叶子结点或删除结点只有一个孩子时，可以合在一起讨论，具体看下面的代码详解（代码略微有点长，需要大家细细品味和思考）：
//删除结点
void delete_node(tree_node *node, int key) {
//判断是否有根结点
if (root == NULL) {
cout << "还没有创建根结点" << endl;
}
//判断当前结点是否为空
if (node == NULL) {
return;
}
else {
//如果找到了要删除的结点
if (node->data == key) {
tree_node *prev = prev_node(root, node, key); //找到删除结点的父节点
temp = NULL;
//1、如果删除结点的右孩子是否为空（包含左孩子也为空即叶子结点的情况）
if (node->right_child == NULL) {
//判断删除结点是否为根结点
if (node == root) {
//判断根结点左孩子是否为空，如果为空则直接删除根结点（因为树中只有一个结点，其左右孩子都是空的）
if (node->left_child == NULL) {
delete[]root;
root = NULL;
return;
}
//否则直接将根结点指针指向当前要删除结点的左孩子，因为右孩子为空不用管
root = prev->left_child;
delete[]prev;
prev = NULL;
return;
}
//如果删除结点不是根结点，则要判断删除结点是其父结点的左孩子还是右孩子
//注意：这里的操作我们用到了prev、temp和node三个指针，不要弄混他们的指向
temp = node; //将临时指针指向要删除的结点
node = node->left_child; //将node指针指向删除结点的左孩子（已知其右孩子为空）
//如果是左孩子（注意这里要先判断父结点左孩子是否为空，如果为空去直接调用会报错）
if (prev->left_child != NULL && prev->left_child->data == temp->data) {
prev->left_child = node; //将父结点的左孩子指向删除结点的左孩子
delete[]temp;
temp = NULL;
}
//如果是右孩子
else {
prev->right_child = node; //将父结点的右孩子指向删除结点的左孩子
delete[]temp;
temp = NULL;
}
}
//2、如果删除结点的右孩子不为空，但是左孩子为空（操作与上面类似）
else if (node->left_child == NULL) {
//判断删除结点是否为根结点
if (node == root) {
//这里不用再判断其右孩子是否为空，因为只有右孩子为空才能进入到这里
root = prev->right_child;
delete[]prev;
prev = NULL;
return;
}
temp = node;
node = node->right_child; //将node指针指向删除结点的右孩子
//判断删除结点是父结点的哪个孩子（同样要先判断指针是否为空）
if (prev->left_child != NULL && prev->left_child->data == key) {
prev->left_child = node; //将父结点的左孩子指向删除结点的右孩子
delete[]temp;
temp = NULL;
} else {
prev->right_child = node; //将父结点的右孩子指向删除结点的右孩子
delete[]temp;
temp = NULL;
}
}
//3、如果删除的结点左右孩子都不为空即在树的中间位置
else {
temp = node; //将temp指向删除结点，作为删除结点左孩子的父结点
tree_node *left_max = temp->left_child; //找到删除结点左孩子中的最大值
//寻找删除结点左孩子中是否有右孩子（如果有，则找到最大值）
while (left_max->right_child != NULL) {
temp = left_max; //随时更新temp指针，使他始终指向left_max的父结点（方便后续操作）
left_max = left_max->right_child;
}
//将左孩子的最大值赋给删除的结点，这样该结点的左孩子的所有值还是小于该结点
node->data = left_max->data;
//判断当初指向删除结点的temp指针的指向是否有改变（注意temp指向的始终是left_max的父结点）
if (temp != node) {
//如果改变了，说明删除结点的左孩子中存在右孩子，则需要将temp的右孩子指向left_max的左孩子
temp->right_child = left_max->left_child;
delete[]left_max;
left_max = NULL;
} else {
//如果没有改变，说明删除结点的左孩子中没有右孩子，则最大值就是删除结点的左孩子，直接将temp指向最大左孩子的左孩子即可
temp->left_child = left_max->left_child;
delete[]left_max;
left_max = NULL;
}
}
}
//如果删除的值比当前结点的值小，则往左孩子递归
else if (key < node->data) {
return delete_node(node->left_child, key);
}
//如果删除的值比当前结点的值大，则往右孩子递归
else if (key > node->data) {
return delete_node(node->right_child, key);
}
}
}
全部代码
#includeusing namespace std; struct tree_node { int data; tree_node *left_child; //左孩子 tree_node *right_child; //右孩子 }; tree_node *root = NULL; //根结点指针 tree_node *temp = NULL; //临时指针 void init_root(int); void insert_child(int); void show_tree(tree_node *); //遍历二叉树 void delete_node(tree_node *, int); tree_node *prev_node(tree_node *, tree_node *, int); int main() { init_root(8); insert_child(2); insert_child(9); insert_child(11); insert_child(23); insert_child(1); insert_child(4); show_tree(root); cout << endl; delete_node(root, 8); show_tree(root); cout << endl; delete_node(root, 2); delete_node(root, 9); delete_node(root, 11); delete_node(root, 23); delete_node(root, 1); show_tree(root); cout << endl; delete_node(root, 4); show_tree(root); cout << endl; delete_node(root, 4); } //初始化根结点 void init_root(int key) { root = new tree_node; root->data = key; root->left_child = root->right_child = NULL; } //插入孩子 void insert_child(int key) { if (root == NULL) { cout << "请先创建根节点" << endl; return; } temp = root; //用临时指针从根结点开始寻找合适的插入位置 while (1) { //如果插入的值比当前结点要小，进入判断 if (key < temp->data) { //如果当前结点的左子树为空，则直接构建新结点进行插入 if (temp->left_child == NULL) { tree_node *new_node = new tree_node; new_node->data = key; new_node->left_child = new_node->right_child = NULL; //将新结点的左指针和右指针都初始化为空 temp->left_child = new_node; //将当前结点的左指针指向新结点 break; } //如果其左子树不为空，则进入其左子树继续进行判断 else { temp = temp->left_child; } } //如果插入的值比当前节点要大，进入判断 else { //如果当前结点的右子树为空，则直接构建新结点继续插入 if (temp->right_child == NULL) { tree_node *new_node = new tree_node; new_node->data = key; new_node->left_child = new_node->right_child = NULL; 将新结点的左指针和右指针都初始化为空 temp->right_child = new_node; //将当前结点的右指针指向新结点 break; } //如果其右子树不为空，则进入其右子树继续进行判断 else { temp = temp->right_child; } } } } //遍历二叉树 void show_tree(tree_node *node) { if (root == NULL) { cout << "还没有创建根结点"; } if (node == NULL) { return; } show_tree(node->left_child); cout << node->data << " "; //中序遍历（用于二叉排序树的输出） show_tree(node->right_child); } //进行查找操作（找到给定结点的父结点） tree_node *prev_node(tree_node *root_node, tree_node *node, int key) { //如果查找的结点就是根结点，直接返回根结点 if (node == root_node) { return node; } //否则，进行递归查找 else { //判断当前遍历的结点的左孩子是否为查找结点 if (root_node->left_child != NULL && root_node->left_child->data == key) { return root_node; } //判断当前遍历的结点的右孩子是否为查找结点 else if (root_node->right_child != NULL && root_node->right_child->data == key) { return root_node; } //如果左右孩子都不是查找结点，则继续往左右孩子进行递归操作 else if (key < root->data) { return prev_node(root_node->left_child, node, key); } else { return prev_node(root_node->right_child, node, key); } } } //删除结点 void delete_node(tree_node *node, int key) { //判断是否有根结点 if (root == NULL) { cout << "还没有创建根结点" << endl; } //判断当前结点是否为空 if (node == NULL) { return; } else { //如果找到了要删除的结点 if (node->data == key) { tree_node *prev = prev_node(root, node, key); //找到删除结点的父节点 temp = NULL; //1、如果删除结点的右孩子是否为空（包含左孩子也为空即叶子结点的情况） if (node->right_child == NULL) { //判断删除结点是否为根结点 if (node == root) { //判断根结点左孩子是否为空，如果为空则直接删除根结点（因为树中只有一个结点，其左右孩子都是空的） if (node->left_child == NULL) { delete[]root; root = NULL; return; } //否则直接将根结点指针指向当前要删除结点的左孩子，因为右孩子为空不用管 root = prev->left_child; delete[]prev; prev = NULL; return; } //如果删除结点不是根结点，则要判断删除结点是其父结点的左孩子还是右孩子 //注意：这里的操作我们用到了prev、temp和node三个指针，不要弄混他们的指向 temp = node; //将临时指针指向要删除的结点 node = node->left_child; //将node指针指向删除结点的左孩子（已知其右孩子为空） //如果是左孩子（注意这里要先判断父结点左孩子是否为空，如果为空去直接调用会报错） if (prev->left_child != NULL && prev->left_child->data == temp->data) { prev->left_child = node; //将父结点的左孩子指向删除结点的左孩子 delete[]temp; temp = NULL; } //如果是右孩子 else { prev->right_child = node; //将父结点的右孩子指向删除结点的左孩子 delete[]temp; temp = NULL; } } //2、如果删除结点的右孩子不为空，但是左孩子为空（操作与上面类似） else if (node->left_child == NULL) { //判断删除结点是否为根结点 if (node == root) { //这里不用再判断其右孩子是否为空，因为只有右孩子为空才能进入到这里 root = prev->right_child; delete[]prev; prev = NULL; return; } temp = node; node = node->right_child; //将node指针指向删除结点的右孩子 //判断删除结点是父结点的哪个孩子（同样要先判断指针是否为空） if (prev->left_child != NULL && prev->left_child->data == key) { prev->left_child = node; //将父结点的左孩子指向删除结点的右孩子 delete[]temp; temp = NULL; } else { prev->right_child = node; //将父结点的右孩子指向删除结点的右孩子 delete[]temp; temp = NULL; } } //3、如果删除的结点左右孩子都不为空即在树的中间位置 else { temp = node; //将temp指向删除结点，作为删除结点左孩子的父结点 tree_node *left_max = temp->left_child; //找到删除结点左孩子中的最大值 //寻找删除结点左孩子中是否有右孩子（如果有，则找到最大值） while (left_max->right_child != NULL) { temp = left_max; //随时更新temp指针，使他始终指向left_max的父结点（方便后续操作） left_max = left_max->right_child; } //将左孩子的最大值赋给删除的结点，这样该结点的左孩子的所有值还是小于该结点 node->data = left_max->data; //判断当初指向删除结点的temp指针的指向是否有改变（注意temp指向的始终是left_max的父结点） if (temp != node) { //如果改变了，说明删除结点的左孩子中存在右孩子，则需要将temp的右孩子指向left_max的左孩子 temp->right_child = left_max->left_child; delete[]left_max; left_max = NULL; } else { //如果没有改变，说明删除结点的左孩子中没有右孩子，则最大值就是删除结点的左孩子，直接将temp指向最大左孩子的左孩子即可 temp->left_child = left_max->left_child; delete[]left_max; left_max = NULL; } } } //如果删除的值比当前结点的值小，则往左孩子递归 else if (key < node->data) { return delete_node(node->left_child, key); } //如果删除的值比当前结点的值大，则往右孩子递归 else if (key > node->data) { return delete_node(node->right_child, key); } } }
如果大家有什么问题的话，欢迎在下方评论区进行讨论哦~
【上一讲】树 - 02 二叉树
【下一讲】树 - 04 线索二叉树
