十四、二叉搜索树
1. 二叉搜索树的概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值。
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值。
它的左右子树也分别为二叉搜索树。
二叉搜索树的查找非常方便，最多查找 树的高度 次就能找到，他还有一个隐藏特点：二叉搜索树的中序遍历是有序的。
2. 二叉搜索树的实现
二叉搜索树，树是一种结构，需要用类来定义，节点也是一种结构，需要另一个类来定义。节点对数来说是完全公开的，所以节点我们使用 struct 。我们创建一个头文件：BinarySearchTree.h ，在里面先编写一个框架出来：
#pragma once // struct BinarySearchTreeNode // 节点结构体 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) {} }; //class BinarySearchTree // 二叉搜索树类 template<class K> class BSTree // 采用缩写 { typedef BSTreeNode<K> Node; public: // private: Node* _root = nullptr; };
查找
二叉搜索树非常适合查找，逻辑也非常简单。通过不断与当前节点比较而选择进入左子树或者右子树。
bool Find(const K& key) { Node* cur = _root; // cur处有节点 while (cur) { // 要查找的值比当前节点的值要小 if (key < cur->_key) { // 前往左子树 cur = cur->_left; } //要查找的值比当前节点的值要大 else if (key > cur->_key) { // 前往右子树 cur = cur->_right; } // 相等时 else { return true; } } // 没找到 return false; }
插入
插入也是比较简单的，当插入的关键字已存在时，现阶段没有多大用处，我们就插入已有的关键字，当关键字不存在时，也是一种查找，当 找到空位置 时，该位置就可以插入。唯一需要注意的是，需要使用一个指针指向插入位置的父节点，否则无法进行节点之间的连接。
bool Insert(const K& key) { // 注意空树 if (_root == nullptr) { _root = new Node(key); return true; } Node* cur = _root; Node* parent = nullptr; while (cur) { if (key < cur->_key) { parent = cur; cur = cur->_left; } else if (key > cur->_key) { parent = cur; cur = cur->_right; } else { // 现阶段不插入相同的值 return false; } } // 创建新节点 cur = new Node(key); if (key < parent->_key) { // 新节点插在左子树 parent->_left = cur; } else { // 新节点插在右子树 parent->_right = cur; } return true; }
中序遍历
中序遍历需要借助当前节点，所以需要一个形参，但是根节点又是属于类的私有成员变量，在外部无法访问，所以我们需要嵌套一层函数来访问。
// private内 void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); std::cout << root->_key << " "; _InOrder(root->_right); } // 套一层函数来获取根节点 // public内 void InOrder() { _InOrder(_root); std::cout << std::endl; }
我们来测试一下：创建一个源文件 Test.cpp。
#include <iostream> #include "BinarySearchTree.h" using namespace std; int main(void) { BSTree<int> t; int a[] = { 8,3,1,10,6,4,7,14,13 }; for (auto e : a) { t.Insert(e); } t.InOrder(); return 0; }
二叉搜索树的中序遍历确实是有序的，看来前面的函数都没有问题。
删除
前面的函数其实都是比较简单的，二叉搜索树的删除会比较困难。二叉搜索树的删除分为三种情况：
- 删除没有孩子节点的节点。
比如删除上图中的 1 4 7 13 。这种情况最简单，直接删掉即可。 - 删除只有一个孩子的节点。
如上图中的 10 14 。这种情况也算是比较简单的，比如说我们要删除 14 。我们只需要将 14 的孩子 托付给 14 的父节点 即可。
- 删除有两个孩子的节点。
比如删除上图中的 8 3 6 。这种情况最为复杂，也最难。这种情况该怎么删除呢？有一种方法叫做 替换删除法 ，比如说我要删除 3 ，我可以从 3 的孩子里找出能够替换掉 3 的节点，即 左子树中的最右侧（最大）的节点，或者右子树中的最左侧（最小）的节点 。这两个节点与被删除的节点替换都可以完成删除操作。
其实情况1和情况2差不多，因为情况1同样可以理解为将 空托付给父节点 。
bool Erase(const K& key) { Node* cur = _root; Node* parent = nullptr; while (cur) { if (key < cur->_key) { parent = cur; cur = cur->_left; } else if (key > cur->_key) { parent = cur; cur = cur->_right; } // 找到了要删除的节点 else { // 左子树为空，托付右子树 if (cur->_left == nullptr) { if (cur == parent->_left) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } delete cur; return true; } // 右子树为空，托付左子树 else if (cur->_right == nullptr) { if (cur == parent->_left) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } delete cur; return true; } // 都不为空使用替换删除法 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; } else { rightMinParent->_right = rightMin->_right; } delete rightMin; return true; } } } return false; }
上面的函数有两个小细节，①假如删除8，则其右孩子 10 就是要删除的节点，所以 rightMinParent 不能初始化为 nullptr。②假如删除8，则其右孩子 10 就是要删除的节点，此时 10 是 8 的右节点，所以 rightMin 不一定是 rightMinParent 的左节点。
测试一下：
#include <iostream> #include "BinarySearchTree.h" using namespace std; int main(void) { BSTree<int> t; int a[] = { 8,3,1,10,6,4,7,14,13 }; for (auto e : a) { t.Insert(e); } t.InOrder(); t.Erase(8); t.InOrder(); return 0; }
已经没有问题了吗？NoNoNo，当要删除的节点是根节点，并且只有左子树或者只有右子树时就会出问题了。此时 Parent 为 nullptr 但是被解引用了，所以我们需要加一下判断：
bool Erase(const K& key) { Node* cur = _root; Node* parent = nullptr; while (cur) { if (key < cur->_key) { parent = cur; cur = cur->_left; } else if (key > cur->_key) { parent = cur; cur = cur->_right; } // 找到了要删除的节点 else { // 左子树为空，托付右子树 if (cur->_left == nullptr) { if (cur == _root) { _root = cur->_right; } else { if (cur == parent->_left) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } } delete cur; return true; } // 右子树为空，托付左子树 else if (cur->_right == nullptr) { if (cur == _root) { _root = cur->_left; } else { if (cur == parent->_left) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } delete cur; return true; } // 都不为空使用替换删除法 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; } else { rightMinParent->_right = rightMin->_right; } delete rightMin; return true; } } } return false; }
拷贝构造
由于默认生成的拷贝构造函数是浅拷贝，直接拷贝构造会导致两个对象指向同一个二叉搜索树，我们要实现深拷贝所以要手动写一个拷贝构造函数。
// 强制生成默认构造函数 BSTree() = default; // 拷贝构造函数 BSTree(const BSTree<K>& t) { _root = Copy(t._root); } // private内 Node* Copy(Node* root) { if (root == nullptr) { return nullptr; } Node* newRoot = new Node(root->_key); newRoot->_left = Copy(root->_left); newRoot->_right = Copy(root->_right); return newRoot; }
析构函数
~BSTree() { Destroy(_root); } // private内 void Destroy(Node* root) { if (root == nullptr) { return; } Destroy(root->_left); Destroy(root->_right); delete root; }
测试一下：
#include <iostream> #include "BinarySearchTree.h" using namespace std; int main(void) { BSTree<int> t; int a[] = { 8,3,1,10,6,4,7,14,13 }; for (auto e : a) { t.Insert(e); } t.InOrder(); BSTree<int> t1(t); t1.InOrder(); return 0; }
赋值重载
BSTree<K>& operator=(BSTree<K> t) { std::swap(_root, t._root); return *this; }
完整代码
#pragma once // struct BinarySearchTreeNode 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) {} }; //class BinarySearchTree template<class K> class BSTree { typedef BSTreeNode<K> Node; public: // 强制生成默认构造函数 BSTree() = default; // 拷贝构造函数 BSTree(const BSTree<K>& t) { _root = Copy(t._root); } BSTree<K>& operator=(BSTree<K> t) { std::swap(_root, t._root); return *this; } // 析构函数 ~BSTree() { Destroy(_root); } bool Insert(const K& key) { if (_root == nullptr) { _root = new Node(key); return true; } Node* cur = _root; Node* parent = nullptr; while (cur) { if (key < cur->_key) { parent = cur; cur = cur->_left; } else if (key > cur->_key) { parent = cur; cur = cur->_right; } else { // 现阶段不插入相同的值 return false; } } // 创建新节点 cur = new Node(key); if (key < parent->_key) { // 新节点插在左子树 parent->_left = cur; } else { // 新节点插在右子树 parent->_right = cur; } return true; } bool Find(const K& key) { Node* cur = _root; // cur处有节点 while (cur) { // 要查找的值比当前节点的值要小 if (key < cur->_key) { // 前往左子树 cur = cur->_left; } //要查找的值比当前节点的值要大 else if (key > cur->_key) { // 前往右子树 cur = cur->_right; } // 相等时 else { return true; } } // 没找到 return false; } void InOrder() { _InOrder(_root); std::cout << std::endl; } bool Erase(const K& key) { Node* cur = _root; Node* parent = nullptr; while (cur) { if (key < cur->_key) { parent = cur; cur = cur->_left; } else if (key > cur->_key) { parent = cur; cur = cur->_right; } // 找到了要删除的节点 else { // 左子树为空，托付右子树 if (cur->_left == nullptr) { if (cur == _root) { _root = cur->_right; } else { if (cur == parent->_left) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } } delete cur; return true; } // 右子树为空，托付左子树 else if (cur->_right == nullptr) { if (cur == _root) { _root = cur->_left; } else { if (cur == parent->_left) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } delete cur; return true; } // 都不为空使用替换删除法 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; } else { rightMinParent->_right = rightMin->_right; } delete rightMin; return true; } } } return false; } private: Node* Copy(Node* root) { if (root == nullptr) { return nullptr; } Node* newRoot = new Node(root->_key); newRoot->_left = Copy(root->_left); newRoot->_right = Copy(root->_right); return newRoot; } void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); std::cout << root->_key << " "; _InOrder(root->_right); } void Destroy(Node* root) { if (root == nullptr) { return; } Destroy(root->_left); Destroy(root->_right); delete root; } Node* _root = nullptr; };
3. 二叉搜索树的应用
K搜索模型
K搜索模型主要运用于想要 快速找到某个值在不在 。比如说门禁系统。
KV搜索模型
KV搜索模型主要运用于想要 通过某个值（key）查找另一个值（value）在不在 。比如说商场车库，通过车牌号找到进车库的时间好用来计费。
上面实现的就是 K搜索模型 ，如何实现 KV搜索模型 呢？其实也不难，节点结构体内多存入一个 value 即可，然后输入 key 的时候也要输入 value。逻辑与 K搜索模型 大差不差。
