⭐上篇文章：31.C++多态4（静态多态，动态多态，虚函数表的存储位置）-CSDN博客

⭐本篇代码：c++学习/18.二叉树进阶-二叉搜索树 · 橘子真甜/c++-learning-of-yzc - 码云 - 开源中国 (gitee.com)

⭐标⭐是比较重要的部分

目录

一. 二叉搜索树的概念

二. 二叉搜索树的插入 

 三. 二叉搜索树的查找

 四. 二叉树的删除

4.1 删除节点右子树为空

4.2 删除节点左子树为空 

4.3 左右孩子均不为空

4.4 删除节点代码 

五. 二叉搜索树的遍历 

六.代码与测试

---

一. 二叉搜索树的概念

        二叉搜索树也称二叉排序树，它有可能是一颗空树。二叉搜索树性质如下：

1 若它有左子树，那么它的左子树所有节点的值小于根节点

2 如它有右子树，那么它的右子树所有节点的值小于根节点

3 它的左右子树也是二叉搜索树

二叉树的代码框架如下：

#pragma once
#include <iostream>
#include <vector>//二叉树节点
template<class K>
struct BSTreeNode
{K _key;BSTreeNode* _left;BSTreeNode* _right;BSTreeNode(const K& key):_key(key), _left(nullptr), _right(nullptr){};
};//二叉树
template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
public:bool Insert(){}bool find(){}bool Delete){}//二叉树不允许修改数据
private:Node* _root;	//根节点
};

二. 二叉搜索树的插入 

假设我们插入的节点为key

若一棵树为空，则直接插入即可

若不为空：

        按照二叉搜索树的性质，插入该节点即可。

如果某一个节点和key值相同，则直接不插入

若某一个节点比key值大，则应该将key插入到该节点的左子树中

若某一个节点比key值小，则应该将key插入到该节点的右子树中

然后在其左右子树中进行判断，直到子树节点为空，然后插入即可

流程图如下：

插入函数的代码如下：

	bool Insert(const K& key){//根节点为空if (!root){_root = new Node(key);return true;}//不为空，根据性质插入数据Node* cur = _root;Node* parent = cur;			//最后cur为空，需要一个节点保存其父节点用于连接while (cur){if (key > cur->_key)	//比当前值大，找其右子树{parent = cur;cur = cur->_right;}else if (key < cur->_key)	//比当前树小，找其左子树{parent = cur;cur = cur->_left;}elsereturn false;	//有相同节点，插入失败}//此时cur为空，cur即为插入的数据cur = new Node(key);if (cur->_key > parent->_key){parent->_right = cur;}else{parent->_left = cur;}return true;}

 三. 二叉搜索树的查找

        二叉搜索树的查找过程和插入过程非常相似。比如在插入的过程中，如果发现值相同，返回true即可，如果为空，则说明没有这个节点，返回false

	bool find(const K& key){if (!_root)return false;Node* cur = _root;while (cur){if (key > cur->_key)cur = cur->_right;else if (key < cur->_key)cur = cur->_left;else return true;}//cur为空，没有key这个节点return false;}

 四. 二叉树的删除

        二叉树的删除比较麻烦。可以分为下面四个情况。

1 该节点无左右子节点：

2 该节点只有左子树：

3 该节点只有右子树

4 该节点有左右子树

实际情况1与情况2或者3是重合的，所以只需考虑三者情况 

4.1 删除节点右子树为空

下面这流程图我们要删除节点9

若删除节点是父亲左孩子，父亲的左指向删除节点的左孩子

若删除节点是父亲的右孩子，父亲的右指向删除节点的左孩子

如果一个节点左右都为空，也满足这种情况

4.2 删除节点左子树为空 

        与上面情况类似

若删除节点是父亲左孩子，父亲的左指向删除节点的右孩子

若删除节点是父亲的右孩子，父亲的右指向删除节点的右孩子

4.3 左右孩子均不为空

        此时需要找到一个节点来替代这个节点，在二叉搜索树中，根据其左子树节点比根节点小，右子树节点比根节点大的性质。如果一给节点左右不为空，只需找出其左子树最大，或者右子树最小来替代这个节点即可。

流程图如下：

4.4 删除节点代码 

//删除bool Erase(const K& key){//1.该节点只有一个孩子//2.该节点没有孩子//3.该节点有三个孩子Node* cur = _root;Node* parent = cur;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else//找到了，开始删除{if (cur->_left == nullptr){//当cur为根的时候要特判if (cur == _root){_root = cur->_right;}if (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}delete cur;cur = nullptr;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}delete cur;cur = nullptr;}else//两边都不为空{//找到左边最大，右边最小与当前值交互即可Node* rightmin = cur->_right;Node* rightminparent = cur;while (rightmin->_left){rightminparent = rightmin;rightmin = rightmin->_left;}cur->_key = rightmin->_key;//如果cur的右孩子是最小的，直接让cur指向右孩子的右孩子即可if (rightmin == cur->_right){cur->_right = rightmin->_right;}else{rightminparent->_left = rightmin->_right;}delete rightmin;rightmin = nullptr;}return true;}}return false;}

五. 二叉搜索树的遍历 

        根据二叉搜索树的性质，如果我们以中序遍历(左根右)，那我们的遍历的时候先是最小的，然后依次遍历更大的。那么最终的排序顺序是有序的！

中序遍历代码如下：

	void _InOrder(const Node* root){if (!root)return;//中序遍历_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}

六.代码与测试

 bstree.h

#pragma once
#include<iostream>
#include<vector>
using namespace std;template<class K>
struct BSTreeNode
{BSTreeNode* _left;BSTreeNode* _right;K _key;//构造函数BSTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}
};template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
public://插入bool Insert(const K& key){//第一次插入if (!_root){_root = new Node(key);return  true;}Node* cur = _root;Node* parent = cur;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(key);if (parent->_key > key){parent->_left = cur;}else{parent->_right = cur;}return true;}//查找bool find(const K& key){if (!_root)return false;Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return true;}}return false;}//删除bool Erase(const K& key){//1.该节点只有一个孩子//2.该节点没有孩子//3.该节点有三个孩子Node* cur = _root;Node* parent = cur;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else//找到了，开始删除{if (cur->_left == nullptr){//当cur为根的时候要特判if (cur == _root){_root = cur->_right;}if (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}delete cur;cur = nullptr;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}delete cur;cur = nullptr;}else//两边都不为空{//找到左边最大，右边最小与当前值交互即可Node* rightmin = cur->_right;Node* rightminparent = cur;while (rightmin->_left){rightminparent = rightmin;rightmin = rightmin->_left;}cur->_key = rightmin->_key;//如果cur的右孩子是最小的，直接让cur指向右孩子的右孩子即可if (rightmin == cur->_right){cur->_right = rightmin->_right;}else{rightminparent->_left = rightmin->_right;}delete rightmin;rightmin = nullptr;}return true;}}return false;}//二叉搜索树不允许修改，修改后会导致二叉树失效//中序遍历void InOrder(){_InOrder(_root);cout << endl;}private:Node* _root = nullptr;void _InOrder(const Node* root){if (!root)return;//中序遍历_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}
};

test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include"bstree.h"void test1()
{BSTree<int> tree;vector<int> arr;for (int i = 0; i < 10; i++){int t = rand() % 10000;arr.push_back(t);tree.Insert(t);}tree.InOrder();for (int i = 0; i <= 9; i++){cout << "删除" << arr[i] << "后:";tree.Erase(arr[i]);tree.InOrder();}
}int main()
{srand((unsigned int)time(0));test1();
}

可以看到，排序的顺序是有序的