数据结构9——二叉搜索树

🥇1.二叉搜索树的概念

二叉搜索树(Binary Search Tree,BST)又称二叉排序树或二叉查找树，其要么是一棵空树，要么具有以下性质：

①：左子树上所有节点的值都小于根节点；

②：右子树上所有节点的值都大于根节点；

③：它的左右子树也都是二叉搜索树。

（于是我们发现：二叉搜索树的中序遍历是一个递增序列。 ）

举例：

（易混淆的点：二叉搜索树是要满足左子树中所有节点的值都要小于根，而不是根的直接子节点小于根即可，即：根的左孩子节点，左子树的孙子节点，重孙节点......都要小于根，右子树也是同样的道理。）

🥇2. 二叉搜索树的实现

使用泛型编程构造出节点和类：

template<class K>
struct BSTreeNode
{typedef BSTreeNode<K> Node;Node* _left;Node* _right;K _key;BSTreeNode(const K& key):_left(nullptr),_right(nullptr),_key(key){}
};template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
public:private:Node* _root = nullptr;
};

🥈2.1 二叉搜索树的查找

根据二叉搜索树的定义，二叉搜索树的查找无非就是拿待查找节点与根节点比较，比根大从右边找，比根小从左边找，最多查找树的高度次；

当找到空还未找到，则这个值在此二叉搜索树中不存在。

具体实现如下：

bool Find(const K& key){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;}

🥈2.2 二叉搜索树的插入

二叉搜索树的插入要注意两种情况：

①树本来就是空树，此时可以直接插入；

②树不为空，先查找到要插入的位置，再插入节点。

具体代码如下：

//插入bool Insert(const K& key){//①树本来就是空树，直接新增节点if (_root == nullptr){_root = new Node(key);return true;}//②树不为空，先查找到要插入的位置，再插入节点Node* parent = nullptr;Node* cur = _root;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->_right = cur;}else{parent->_left = cur;}return true;}

🥈2.3 二叉搜索树的删除

二叉搜索树的删除较为复杂，需要分情况讨论：

情况①：要删除的节点没有孩子

情况②：要删除的节点只有左孩子；

情况③：要删除的节点只有右孩子；

情况④：要删除的节点有两个孩子

实际操作中，可以将①②和①③合并，所以代码实现就只有三种情况：

情况①：要删除的节点没有左孩子（此节点只有右孩子或没有孩子）；

情况②：要删除的节点没有右孩子（此节点只有左孩子或没有孩子）；

①和②可以直接删除目标节点，然后将目标节点的孩子托付给爷爷；

情况③：要删除的节点有两个孩子；

③由于存在两个孩子，所以此时就不能再用“托孤”的方法了，我们可以采用替换法删除：找到一个合适的值换掉要删除的值，然后再删除这个“合适的值”，最后再“托孤”。那么这个所谓“合适的值”该如何寻找呢？到底多合适才算合适呢？

我们知道，二叉搜索树都满足左节点比根小，右节点比根大，换一种说法，根就是这组数据的“中位数”，当删除这个“中位数”时，我们只需再找一个中位数左右两边的值作为新的“中位数”就行了呀！

我们知道二叉搜索树的中序遍历就是一个递增序列，所以：

根左边的值是根的左子树的最右节点（以下图为例，8的左子树的最右节点就是7）；

根右边的值是根的右子树的最左节点（以下图为例，8的右子树的最左节点就是10）。

（我们以寻找根的右子树的最左节点作为替换值进行代码实现）

具体代码如下：

//删除bool Erase(const K& key){//1.先查找要删除的节点Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}//2.查找到要删除的节点else{//①要删除的节点没有左孩子（此节点只有右孩子或没有孩子）if (cur->_left == nullptr){if (cur == _root)//根节点单独处理{_root = cur->_right;}else//只有右孩子，将右孩子托付给爷爷（如上图的节点10）“托孤”{if (cur == parent->_right)//判断父亲是爷爷的左孩子还是右孩子，以便于继承父亲的位置{parent->_right = cur->_right;}else{parent->_left = cur->_right;}}delete cur;return true;}//②要删除的节点没有右孩子（此节点只有左孩子或没有孩子）else if (cur->_right == nullptr){if (cur == _root)//根节点单独处理{_root = cur->_left;}else//只有左孩子，将左孩子托付给爷爷（如上图的节点14）“托孤”{if (cur == parent->_right)//判断父亲是爷爷的左孩子还是右孩子，以便于继承父亲的位置{parent->_right = cur->_left;}else{parent->_left = cur->_left;}}delete cur;return true;}//③要删除的节点有两个孩子（如上图的节点3、6、8）else{// 替换法// 寻找右子树的最左值作为替换值Node* rightMinParent = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinParent = rightMin;rightMin = rightMin->_left;}//已找到替换值，开始替换cur->_key = rightMin->_key;//“托孤”过程if (rightMin == rightMinParent->_left)rightMinParent->_left = rightMin->_right;elserightMinParent->_right = rightMin->_right;delete rightMin;return true;}}}return false;}//遍历void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}void InOrder(){_InOrder(_root);}

🥈测试

int main()
{BSTree<int> t;int a[] = { 3,6,9,1,4,2,7,5,8,10 };for (auto e : a){t.Insert(e);}t.InOrder();t.Erase(9);t.InOrder();t.Insert(52);t.InOrder();return 0;
}

结果如图：

🥇3.二叉搜索树的应用

学了二叉搜索树，可是二叉搜索树到底有什么实际的用途呢？接下来就介绍二叉搜索树的两个模型：K模型和KV模型。

🥈3.1 K 模型

K模型：只有Key作为关键码，结构中只需要存储Key，关键码即为需要搜索到的值。

比如：学校的门禁通过扫脸分辨此人是否为校内人员，具体方式如下：

以每个学生的脸部特征作为Key，构建一棵二叉搜索树；

在二叉搜索树中检索该学生是否存在，存在则开门禁，不存在则不开门禁。

具体实现如下：（为方便演示，这里以学生姓名设置Key，K模型的代码与2中二叉搜索树的实现相似，不同的是需要修改Find函数的返回值和返回类型）

template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
public://查找Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return cur;}}return nullptr;}private:Node* _root = nullptr;
};int main()
{BSTree<string> Stu;Stu.Insert("张三");Stu.Insert("李四");Stu.Insert("王五");Stu.Insert("赵六");Stu.Insert("田七");string str;while (cin >> str){auto ret = Stu.Find(str);if (ret){cout << "开门" << endl;}else{cout << "保持关闭" << endl;}}return 0;
}

结果如图：

🥈3.2 KV模型

KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。

KV模型相较于K模型更常见，比如：查找英汉词典中英文与中文的对应关系<English,Chinese>；查找学生姓名与性别的对应关系<Name,Sex>。

还以后者为例进行代码实现：

//KV模型
namespace Key_Value
{template<class K,class V>struct BSTreeNode{typedef BSTreeNode<K, V> Node;Node* _left;Node* _right;K _key;V _value;BSTreeNode(const K& key,const V& value):_left(nullptr), _right(nullptr), _key(key), _value(value){}};template<class K,class V>class BSTree{typedef BSTreeNode<K, V> Node;public://查找Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return cur;}}return nullptr;}//插入bool Insert(const K& key,const V& value){//①树本来就是空树，直接新增节点if (_root == nullptr){_root = new Node(key, value);return true;}//②树不为空，先查找到要插入的位置，再插入节点Node* parent = nullptr;Node* cur = _root;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, value);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}//删除bool Erase(const K& key){//1.先查找要删除的节点Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}//2.查找到要删除的节点else{//①要删除的节点没有左孩子（此节点只有右孩子或没有孩子）if (cur->_left == nullptr){if (cur == _root)//根节点单独处理{_root = cur->_right;}else//只有右孩子，将右孩子托付给爷爷（如上图的节点10）“托孤”{if (cur == parent->_right)//判断父亲是爷爷的左孩子还是右孩子，以便于继承父亲的位置{parent->_right = cur->_right;}else{parent->_left = cur->_right;}}delete cur;return true;}//②要删除的节点没有右孩子（此节点只有左孩子或没有孩子）else if (cur->_right == nullptr){if (cur == _root)//根节点单独处理{_root = cur->_left;}else//只有左孩子，将左孩子托付给爷爷（如上图的节点14）“托孤”{if (cur == parent->_right)//判断父亲是爷爷的左孩子还是右孩子，以便于继承父亲的位置{parent->_right = cur->_left;}else{parent->_left = cur->_left;}}delete cur;return true;}//③要删除的节点有两个孩子（如上图的节点3、6、8）else{// 替换法// 寻找右子树的最左值作为替换值Node* rightMinParent = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinParent = rightMin;rightMin = rightMin->_left;}//已找到替换值，开始替换cur->_key = rightMin->_key;//“托孤”过程if (rightMin == rightMinParent->_left)rightMinParent->_left = rightMin->_right;elserightMinParent->_right = rightMin->_right;delete rightMin;return true;}}}return false;}//遍历void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);std::cout << root->_key << " ";_InOrder(root->_right);}void InOrder(){_InOrder(_root);std::cout << std::endl;}private:Node* _root = nullptr;};
}int main()
{Key_Value::BSTree<string, string> Stu;Stu.Insert("张三", "男");Stu.Insert("李四", "女");Stu.Insert("王五", "男");Stu.Insert("赵六", "女");Stu.Insert("田七", "女");string str;while (cin >> str){auto ret = Stu.Find(str);if (ret){cout << ret->_value << endl;}else{cout << "查无此人" << endl;}}return 0;
}

结果如图：