二叉搜索树

内容安排说明

二叉树在前面 C 数据结构阶段已经讲过，本节取名二叉树进阶是因为：

1. map 和 set 特性需要 先铺垫二叉搜索树，而二叉搜索树也是一种树形结构

2. 二叉搜索树的特性了解，有助于更好的理解 map 和 set 的特性

3. 二叉树中部分面试题稍微有点难度 ，在前面讲解 大家不容易接受 ，且时间长容易忘

4. 有些 OJ 题使用 C 语言方式实现比较麻烦，比如有些地方要返回动态开辟的二维数组，非常麻 烦。

因此本节借二叉树搜索树，对二叉树部分进行收尾总结。

二叉搜索树（概念）

概念：任意左孩子比根小，右孩子比根大

二叉搜索树模拟实现讲解

这里是把二叉搜索树的原理以及实现精讲一下，代码放在最后

K模型

首先将结点的构造函数写，方便初始化给值

根节点指针默认初始化为nullptr；

这里强制生成默认构造，要不然定义对象时会和拷贝构造发生冲突

可以理解为拷贝完左子树连接到左节点，拷贝完右子树连接到右结点，最后返回自身结点给上一层，返回条件是遇到空

拷贝构造，就是将已知对象的结点拷贝构造一份，并且连接起来以后赋值给新对象的私有成员_root，这个过程不难理解，就是new一个节点，左子树递归-》右子树递归-》返回给上一层，返回条件就是结点为空。

进入递归，当进入到二叉搜索树左下那个结点时，左右孩子指向空，自身返回给上一层的左，然后进入右子树递归，重复过程，层层返回，最后返回给整颗树的根，每一个子树都满足左子树递归-》右子树递归-》返回根给上一层，以这样的思路去思考二叉树递归方面的题，大问题划分为小问题就好了，最后拷贝构造完返回给外边的_root

感兴趣可以看看我之前写的二叉树初阶，介绍了如何分析二叉树递归

二叉树和堆-CSDN博客https://blog.csdn.net/eixjdj/article/details/145232674?spm=1001.2014.3001.5501https://blog.csdn.net/eixjdj/article/details/145232674?spm=1001.2014.3001.5501https://blog.csdn.net/eixjdj/article/details/145232674?spm=1001.2014.3001.5501https://blog.csdn.net/eixjdj/article/details/145232674?spm=1001.2014.3001.5501

赋值拷贝很简单，和之前STL讲的都是一个道理，先利用拷贝构造一个t，交换之后出作用域t自动销毁，并且也完成了赋值拷贝的任务

析构很简单的递归，递归左子树-》递归右子树-》删除根

先讲非递归版本

简单的插入逻辑，如果根为空，直接new一个节点，返回插入成功

不为空，接着插入key这个节点，定义cur指针和parent指针方便以后链接，key大于树种的key往右找，小于往左找，找到返回false意思是不用重复插入，找到要插入的地方cur会指向空，跳出循环，大于插在右边，小于插在左边就行了（记得和父亲链接）

查找很简单，大于往右找，小于往左找，找到返回，找不到返回错误

删除逻辑有些复杂，细节比较多，我慢慢分析

定义父母指针和cur指针为了方便遍历和连接，一开始还是先找要删除的节点，找到之后分为三种情况，那个节点有0个孩子，1个孩子和2个孩子，其实0个1个孩子可以都理解成一个逻辑，如果要删除的结点左孩子为空，是父亲的左就把右孩子给父亲的左，是父亲的右就把右孩子给父亲的右，删除节点，就完成1个孩子的删除（是父亲的右和刚才的逻辑反着来很简单，如果删除0个孩子也就是叶子结点可以当成一个孩子的结点考虑，相当于把空指针给父亲原理也是一样的）

还有一个特例，当要删除根节点并且左右孩子有一个为空的时候，父亲指针一直是空，会解引用空指针，所以开头直接判断如果删除根节点指针，直接赋值_root为根节点的左/右孩子（左孩子为空赋值右孩子，右孩子为空赋值左孩子）

最后一种情况比较复杂，就是删除2个孩子

这里采用替换法删除，注意父亲指针不能是空，如果那个要替换过去的结点指针没有左孩子，循环根本没进去，父亲指针就还是空指针，下边会解引用空指针。

这里将指针置为cur，就算没有进去循环，也能完成链接任务

找到左子树最右结点或者右子树最左结点和要删除的值替换（这两个任意选一个交换就行，只要意义对），替换之后还是满足二叉搜索树的特点。

替换之后如果删除节点在父亲左边，将父亲左连接删除节点的孩子

如果删除节点在父亲右边，将父亲右连接删除节点的孩子，就完成了删除（记得要delete掉要删除的空间，要不然会内存泄漏）

最后有一个返回false，因为当树是空的时候，前面的循环不会进去，直接返回失败就行

并且如果要删除的值找不到循环会结束（循环结束条件就是cur为空，意思是找完了还没找到就会跳出来）也会返回false

中序遍历也很简单。就不解释了，这里封装一下是因为外边不能传类的私有参数

注意二叉搜索树的中序遍历是升序（左根右顺序赋值，不管是子树还是整颗树都是这样）

刚才讲的是非递归版本，现在讲一下递归版本的写法

递归版本的查找，很简单，比key小往右找，比key大往左找，找到返回true（层层返回），找不到返回false，层层返回

插入有点东西，注意参数部分加了一个引用，目的是为了不用父母指针就能链接到new出来的结点上，将每个节点连接起来

Eugene如果根是空，new一个节点直接赋值给root（这里的root就是_root的引用，可以改变外部的节点）并且返回插入成功

如果根不为空，插入的值大于key就往右找，小于往左找，找到空说明找到要连接的地方了，直接new赋值，就可以改变外部的结点（新增一个节点）了，最后找到返回false，因为找到了就没必要插入了（这里的返回值在map，set部分有用后期会说）

删除版本来了

这里增删查改有些要定义父亲指针原因是方便记录插入地方的父亲，方便链接

这里树为空是递归出口，有2个作用，1是可以当树是空树的时候直接返回，2是找到最后没找到的会返回给第一层

树非空就会进入下边的条件，先找要删除的节点，

当找到要删除的key所在结点后会进入这个else，先定义一个del意义是记录要删除的节点

下边的和非递归版本很相似，因为我们参数加了一个引用，所以会好写一些

孩子有0个或1个时候，当右树为空的时候，直接把他的左孩子给给root，root是指向要删除节点的指针的别名，赋值可以完美衔接将两个节点连接，并且连接以后还是满足二叉搜索树的特点，最后出来会删除del并且返回true删除成功；当左树是空是一个道理

当要删除结点有2个孩子时会采用替换法删除

假设删除3，找到最右孩子的最左节点之后，交换值并且return递归root的右，相当于复用一下前面的逻辑，一直循环直到真正删除要删除的值返回给上一层，最后有delete会删除该删除的结点

简单说一下key_vaule模型，和key没有本质区别，可以看到构造函数只是多一个值

查找逻辑略微有变化，找到返回指针，找不到返回nullptr，因为查找要找到key对应的vaule

插入有2个参数，因为要存储两个值

删除完全没有变化，因为删除只要传递key就够了，不涉及value

测试增删查改逻辑

测试非递归版本，可以看到没啥问题
递归版本也没有问题

拷贝构造也没问题，前面都讲过

这里测试key_value模型，当输入的key是对的，会返回指针，如果非空证明有这个值

打印value反之打印无

string类型的比较会调用库里的运算符重载，会按照ASCLL码进行挨个比较

最后看一个有意思的测试样例，统计水果次数

如果返回值为空，说明是第一次插入，插入进去水果和次数

如果返回值不为空，说明插入过了，次数++，就能完美统计水果次数

key和key_value模型（了解）

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

比如： 给一个单词 word ，判断该单词是否拼写正确 ，具体方式如下：

以词库中所有单词集合中的每个单词作为 key ，构建一棵二叉搜索树

在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

2. KV 模型：每一个关键码 key ，都有与之对应的值 Value ，即 <Key, Value> 的键值对 。该种方式在现实生活中非常常见：比如英汉词典就是英文与中文的对应关系 ，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese> 就构成一种键值对；

再比如 统计单词次数 ，统计成功后，给定单词就可快速找到其出现的次数， 单词与其出

现次数就是 <word, count> 就构成一种键值对 。

二叉搜索树的性能分析

最优情况下，二叉搜索树为完全二叉树 ( 或者接近完全二叉树 ) ，其平均比较次数为： log N

最差情况下，二叉搜索树退化为单支树 ( 或者类似单支 ) ，其平均比较次数为：N（类似链表）

问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，二叉搜索树的性能都能达到最优？那么我们后续章节学习的 AVL树和红黑树就可以上场了。（ avl和红黑是二叉搜索树的进阶提升，弥补了单支树查找效率低的缺点，并且延续二叉搜索树的优点）

二叉搜索树面试题（感兴趣可以看看）

606. 根据二叉树创建字符串 - 力扣（LeetCode）

102. 二叉树的层序遍历 - 力扣（LeetCode）

107. 二叉树的层序遍历 II - 力扣（LeetCode）

236. 二叉树的最近公共祖先 - 力扣（LeetCode）

二叉搜索树与双向链表_牛客题霸_牛客网

105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）

144. 二叉树的前序遍历 - 力扣（LeetCode）

94. 二叉树的中序遍历 - 力扣（LeetCode）

145. 二叉树的后序遍历 - 力扣（LeetCode）

二叉搜索树完整代码

BSTree.h

#pragma once
namespace key
{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 BinarySearchTreetemplate<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){swap(_root, t._root);return *this;}~BSTree(){Destroy(_root);}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;}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;}bool Erase(const K& key){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{if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{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{if (cur == parent->_right){parent->_right = cur->_left;}else{parent->_left = 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;elserightMinParent->_right = rightMin->_right;delete rightMin;return true;}}}return false;}void InOrder(){_InOrder(_root);cout << endl;}//bool FindR(const K& key){return _FindR(_root, key);}bool InsertR(const K& key){return _InsertR(_root, key);}bool EraseR(const K& key){return _EraseR(_root, key);}private:void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}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;}bool _EraseR(Node*& root, const K& key){if (root == nullptr)return false;if (root->_key < key){return _EraseR(root->_right, key);}else if (root->_key > key){return _EraseR(root->_left, key);}else{Node* del = root;if (root->_right == nullptr){root = root->_left;}else if (root->_left == nullptr){root = root->_right;}else{Node* rightMin = root->_right;while (rightMin->_left){rightMin = rightMin->_left;}swap(root->_key, rightMin->_key);return _EraseR(root->_right, key);}delete del;return true;}}bool _InsertR(Node*& root, const K& key){if (root == nullptr){root = new Node(key);return true;}if (root->_key < key){return _InsertR(root->_right, key);}else if (root->_key > key){return _InsertR(root->_left, key);}else{return false;}}bool _FindR(Node* root, const K& key){if (root == nullptr)return false;if (root->_key < key){return _FindR(root->_right, key);}else if (root->_key > key){return _FindR(root->_left, key);}else{return true;}}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}private:Node* _root = nullptr;};
}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: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;}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 Erase(const K& key){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{if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{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{if (cur == parent->_right){parent->_right = cur->_left;}else{parent->_left = 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;elserightMinParent->_right = rightMin->_right;delete rightMin;return true;}}}return false;}void InOrder(){_InOrder(_root);cout << endl;}private:void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << ":" << root->_value << endl;_InOrder(root->_right);}private:Node* _root = nullptr;};
}

Test.cpp

#include<iostream>
using namespace std;#include"BSTree.h"//int main()
//{
//	key::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();
//
//	t.Erase(14);
//	t.InOrder();
//
//	t.Erase(4);
//	t.InOrder();
//
//	t.Erase(6);
//	t.InOrder();
//
//	for (auto e : a)
//	{
//		t.Erase(e);
//		t.InOrder();
//	}
//
//	t.InOrder();
//
//	return 0;
//}//
//int main()
//{
//	key::BSTree<int> t;
//	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
//	for (auto e : a)
//	{
//		t.InsertR(e);
//	}
//
//	t.InOrder();
//
//	t.EraseR(8);
//	t.InOrder();
//
//	t.EraseR(14);
//	t.InOrder();
//
//	t.EraseR(4);
//	t.InOrder();
//
//	t.EraseR(6);
//	t.InOrder();
//
//	for (auto e : a)
//	{
//		t.EraseR(e);
//		t.InOrder();
//	}
//
//	t.InOrder();
//
//	return 0;
//}//
//int main()
//{
//	key::BSTree<int> t;
//	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
//	for (auto e : a)
//	{
//		t.InsertR(e);
//	}
//	t.InOrder();
//
//	key::BSTree<int> t1(t);
//	t1.InOrder();
//
//	return 0;
//}//int main()
//{
//	key_value::BSTree<string, string> dict;
//	dict.Insert("sort", "排序");
//	dict.Insert("left", "左边");
//	dict.Insert("right", "右边");
//	dict.Insert("string", "字符串");
//
//	string str;
//	while (cin>>str)
//	{
//		auto ret = dict.Find(str);
//		if(ret)
//		{
//			cout << ret->_value << endl;
//		}
//		else
//		{
//			cout << "无此单词" << endl;
//		}
//	}
//
//	return 0;
//}int main()
{string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "西瓜", "香蕉", "草莓" };key_value::BSTree<string, int> t;for (auto& e : arr){auto ret = t.Find(e);if (ret == nullptr){// 第一次出现t.Insert(e, 1);}else{ret->_value++;}}t.InOrder();return 0;
}