一、二叉搜索树的概念

二叉搜索树又称二叉排序树，它具有一下性质：

• 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值；
• 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值；
• 它的左右子树也分别为二叉搜索树。

注意：空树可以是任意类型的树，所以空树也是一颗二叉搜索树。

二、二叉搜索树的优点

二叉搜索树是日常生活中非常常用的一种数据结构，它可以用来排序 – 由于二叉搜索树的左子树都小于根，右子树都大于根，所以如果对二叉搜索树进行中序遍历得到的数据天然就是有序的。

不过二叉搜索树最主要的用途是进行查找 – 由于二叉搜索树结构的特性，进行查找时每次比较都能直接排除掉整个左子树/右子树的数据，但由于关键码的插入次序会构建出不同的二叉搜索树，所以其查找性能如下：

• 最优情况下，二叉搜索树为完全二叉树 (或者接近完全二叉树)，其平均比较次数为 O(logN)。
• 最差情况下，二叉搜索树退化为单支树( 或者类似单支)，其平均比较次数为 O(N)。
• 所以，二叉搜索树进行查找的时间复杂度为 O(N)。

可能有的同学会想，既然二叉搜索树查找的时间复杂度为 O(N)，那我们为什么不直接用二分查找呢？毕竟二分查找的时间复杂度可是 O(logN)，这是因为二分查找存在许多限制：

• 二分查找要求数据必须有序；
• 二分查找使用顺序表进行数据存储，插入、删除数据效率低，而在实际开发中，我们是要经常插入删除数据的；

而且，只有当数据有序或接近有序时二叉搜索树查找数据的时间复杂度才为 O(N)，大部分情况下查找效率都是要远高于 O(N) 的；同时，在实际开发中我们用的并不是单纯的二叉搜索树树，而是它的改进版 – 二叉搜索平衡树 (AVL树) ，即插入数据后对二叉搜索树进行调整，让其左右子树尽量变得平衡，这样，二叉搜索树的查找效率就几乎等于 O(logN) 了。

注：关于二叉搜索平衡树我们将在下一节介绍。

三、二叉搜索树的操作及实现

我们下面讲的二叉搜索树的操作均以数组 a 中的数据为例：

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

1、二叉搜索树的查找

a. 从根开始比较查找，如果比根大就往右边走查找，比根小则往左边走查找；

b. 最多查找高度次，如果走到到空，还没找到，则这个值不存在。

其代码实现如下：

bool find(const K& key) {Node* cur = _root;while (cur) {if (key > cur->_key)cur = cur->_right;else if (key < cur->_key)cur = cur->_left;elsereturn true;}//cur为空还没找到说明没有这个值return false;
}

2、二叉树的插入

a. 如果根为空，则直接将新增节点作为根节点；

b. 如果根不为空，则按二叉树性质查找插入位置 – 比根大就往右边走，比根小就往左边走，直到找到为空的位置，然后插入；

c. 如果查找遇到过程中遇到与新增节点 key 值相同的节点直接返回 false，这是因为 K 模型中不允许出现冗余节点 (key 值相同的节点)；

注意：在遍历查找插入位置的过程中，我们需要记录父节点的地址，因为我们需要将新增节点链接到二叉搜索树中。

代码实现如下：

bool insert(const K& key) {if (_root == nullptr) {_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;while (cur) {if (key > cur->_key) {  //比根大就往右子树放parent = cur;cur = cur->_right;}else if (key < cur->_key) {  //比根小往左放parent = cur;cur = cur->_left;}else {  //二叉搜索树中不允许有冗余节点，相等直接插入失败return false;}}//空位就是key的插入位置Node* newnode = new Node(key);if (key > parent->_key)parent->_right = newnode;else parent->_left = newnode;return true;
}

3、二叉搜索树的删除

二叉搜索树的删除是二叉搜索树中最复杂的部分，因为它有非常多的细节，如果校招时面试官要让你手撕一个二叉搜索树，多半会直接让你写一个二叉搜索树的删除。

二叉搜索树的删除过程如下：

a. 先查找该元素是否存在于二叉搜索树中，如果不存在，直接返回 false；

b. 如果存在，则开始删除，删除一共可以分为以下三种情况：

1. 要删除的节点为叶节点，此时我们只需要让父节点的 left/right 指向空，然后 delete 叶节点即可 – 直接删除；
2. 要删除的节点只有左孩子或只有右孩子，此时我们需要将该节点的子节点托孤给父节点，然后再 delete 该节点 – 直接删除；
3. 要删除的节点既有左孩子又有右孩子，此时我们需要先将该节点与左子树的最大/最右节点或右子树的最小/最左节点进行交换，然后再 delete 掉被替换的最左节点/最右节点 – 替换删除。

上面这三种情况对应着下图这四个元素的删除情况：

需要注意的是，第一种情况可以归类到第二种情况中去，因为左右都为空也属于左为空或右为空的情况；至于替换删除时为什么是找左子树的最大节点和右子树的最小节点，这是由二叉搜索树的性质决定的：

a. 二叉搜索树左孩子小于根小于右孩子，所以左子树的最大节点一定大于当前节点的其余左子树节点，小于当前节点的所有右子树节点，那么将它替换掉当前节点后二叉搜索树仍然能保存二叉搜索树的结构 – 左子树节点全部小于根，右子树节点全部大于根；选右子树最小节点同理。

b. 与上图中的8为例，8左子树的最大节点为7，将8替换为7后左子树的其余节点全小于7，右子树全大于7；将8替换为右子树的最小节点10后，左子树全部小于10，右子树其余节点全大于10。

代码实现如下：

//删除有三种情况：
//1.删除的节点为叶结点--将叶节点的父节点的left或right置空，然后直接delete叶节点 即可(直接删除)
//2.删除的节点有一个子节点--将节点的子节点托孤给父节点，然后直接delete即可 (直接删除)
//3.删除的节点有两个子节点--将该节点与左子树的最大/最右节点或右子树的最小/最左节点进行交换，然后delete最右节点/最左节点即可 (替换删除)
//注：情况1可以归类为情况2--左右都为空属于节点左为空/右为空的情况
bool erase(const K& key) {Node* parent = nullptr;Node* cur = _root;while (cur) {//先找节点if (key > cur->_key) {parent = cur;cur = cur->_right;}else if (key < cur->_key) {parent = cur;cur = cur->_left;}else {  //找到了就开始删除//1.左为空--如果我是父的左，就让父的左指向我的右；如果我是父的右，就让父的右指向我的右if (cur->_left == nullptr){//如果cur==root需要单独处理if (cur == _root)_root = cur->_right;else{if (cur == parent->_left)parent->_left = cur->_right;else parent->_right = cur->_right;}delete cur;}//2.右为空--如果我是父的左，就让父的左指向我的左；如果我是父的右，就让父的右指向我的左else if (cur->_right == nullptr){//cur==root的情况需要单独处理if (cur == _root)_root = cur->_left;else{if (cur == parent->_left)parent->_left = cur->_left;else parent->_right = cur->_left;}delete cur;}//3.左右都不为空--找左树的最大节点或右树的最小节点进行替换删除(有很多细节，需要特别注意)else{//找右树的最小节点，即最左节点Node* minRight = cur->_right;//最左节点只是没有左孩子，还是可能有右孩子，所以这里需要记录父节点，方便后面继续托孤//同时，这里parent不能初始化为空，因为cur->_right可能直接就为右子树的最左节点，此时不会进循环，parent也不会被赋值(对应上图中删除8的场景)Node* parent = cur;while (minRight->_left)  //左为空即为最左节点{parent = minRight;minRight = minRight->_left;}//替换minRight和cur节点的值(直接将minRight值赋给cur就行，因为minRight最终会被释放掉)cur->_key = minRight->_key;//minRight可能是父的左节点，也可能是父的右节点，所以这里还需要判断//当cur->_right == minRight时，minRight托孤给父节点的右if (parent->_left == minRight)parent->_left = minRight->_right;else parent->_right = minRight->_right;delete minRight;}return true;}}//找不到返回falsereturn false;
}

4、二叉搜索树的递归实现

二叉搜索树的查找、插入和删除还可以实现为递归版本，虽然我们说，只要能写成循环就一定不要写成递归，因为函数调用要建立栈帧，递归调用时栈帧开销会很大。但是递归版本这里用引用做参数设计的十分巧妙，几乎完美解决了父节点链接子节点的问题，所以我们还是可以学习一下。

递归代码如下：

//查找递归版本
bool findR(const K& key) {return _findR(_root, key);
}//查找递归版本
bool _findR(Node* root, const K& key) {if (root == nullptr)return false;if (key > root->_key)return _findR(root->_right, key);else if (key < root->_key)return _findR(root->_left, key);elsereturn true;
}//插入递归版本
bool insertR(const K& key) {return _insertR(_root, key);
}//插入递归版本
//为了解决父节点无法链接子节点的问题，我们这里把root定义实参的引用
bool _insertR(Node*& root, const K& key) {if (root == nullptr) {root = new Node(key);return true;}if (key > root->_key)return _insertR(root->_right, key);else if (key < root->_key)return _insertR(root->_left, key);elsereturn false;
}//删除递归版本
bool eraseR(const K& key) {return _eraseR(_root, key);
}//删除递归版本
//为了解决父节点链接的问题，这里还是使用引用--巧用引用
bool _eraseR(Node*& root, const K& key) {if (root == nullptr)return false;if (key > root->_key)return _eraseR(root->_right, key);else if (key < root->_key)return _eraseR(root->_left, key);else  //删除{Node* del = root;//由于root是实参的别名，所以这里的root本来就是父节点的左孩子或右孩子//所以我们直接用root的left/right覆盖原来的root就自动链接上了，而不用再去找父节点//并且这里也适用于root为根的情况，不用单独处理if (root->_left == nullptr)  //左为空root = root->_right;else if (root->_right == nullptr)  //右为空root = root->_left;else  //左右都不为空{//找右子树最小节点进行替换Node* minRight = root->_right;while (minRight->_left) {minRight = minRight->_left;}//交换root和minRight的值std::swap(root->_key, minRight->_key);//此时key成为了右子树的最小节点，所以key的左子树一定为空，满足情况1//所以我们就可以让右子树第一个节点做根，然后到右子树中去递归删除key，复用前面的代码//此处不能传递minRight，因为minRight是一个局部变量，形参以它为别名无意义return _eraseR(root->_right, key);}delete del;return true;}
}

注：之所以要在 findR 中调用 _findR，insertR 中调 _insertR，eraseR 中调用 _eraseR 是因为这些操作都需要从根节点 _root 开始比较，而用户在类外调用这些函数时是无法取出 _root 作为实参进行传递的，所以我们通过子函数的方式来传递 _root。

5、模拟实现完整代码

BSTree.h：

#pragma once
#include <algorithm>
using std::cout;template<class K>
struct BSTreeNode {BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;BSTreeNode(int key = K()): _key(key), _left(nullptr), _right(nullptr){}
};template<class K>
class BSTree {typedef BSTreeNode<K> Node;
public:BSTree(): _root(nullptr){}~BSTree() {//递归析构每一个节点destory(_root);_root = nullptr;}BSTree(const BSTree<K>& t) {//递归拷贝每一个节点_root = copy(t._root);}//赋值重载--复用拷贝构造BSTree<K>& operator=(BSTree<K> t) {std::swap(_root, t._root);return *this;}bool insert(const K& key) {if (_root == nullptr) {_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;while (cur) {if (key > cur->_key) {  //比根大就往右子树放parent = cur;cur = cur->_right;}else if (key < cur->_key) {  //比根小往左放parent = cur;cur = cur->_left;}else {  //二叉搜索树中不允许有冗余节点，相等直接插入失败return false;}}//空位就是key的插入位置Node* newnode = new Node(key);if (key > parent->_key)parent->_right = newnode;else parent->_left = newnode;return true;}//插入递归版本bool insertR(const K& key) {return _insertR(_root, key);}bool find(const K& key) {Node* cur = _root;while (cur) {if (key > cur->_key)cur = cur->_right;else if (key < cur->_key)cur = cur->_left;elsereturn true;}//cur为空说明找不到return false;}//查找递归版本bool findR(const K& key) {return _findR(_root, key);}//删除有三种情况：//1.删除的节点为叶结点--将叶节点的父节点的left或right置空，然后直接delete叶节点 即可(直接删除)//2.删除的节点有一个子节点--将节点的子节点托孤给父节点，然后直接delete即可 (直接删除)//3.删除的节点有两个子节点--将该节点与左子树的最大/最右节点或右子树的最小/最左节点进行交换，然后delete最右节点/最左节点即可 (替换删除)//注：情况1可以归类为情况2--左右都为空属于节点左为空/右为空的情况bool erase(const K& key) {Node* parent = nullptr;Node* cur = _root;while (cur) {//先找节点if (key > cur->_key) {parent = cur;cur = cur->_right;}else if (key < cur->_key) {parent = cur;cur = cur->_left;}else {  //找到了就开始删除//1.左为空--如果我是父的左，就让父的左指向我的右；如果我是父的右，就让父的右指向我的右if (cur->_left == nullptr){//如果cur==root需要单独处理if (cur == _root)_root = cur->_right;else{if (cur == parent->_left)parent->_left = cur->_right;else parent->_right = cur->_right;}delete cur;}//2.右为空--如果我是父的左，就让父的左指向我的左；如果我是父的右，就让父的右指向我的左else if (cur->_right == nullptr){//cur==root的情况需要单独处理if (cur == _root)_root = cur->_left;else{if (cur == parent->_left)parent->_left = cur->_left;else parent->_right = cur->_left;}delete cur;}//3.左右都不为空--找左树的最大节点或右树的最小节点进行替换删除(有很多细节，需要特别注意)else{//找右树的最小节点，即最左节点Node* minRight = cur->_right;//最左节点只是没有左孩子，还是可能有右孩子，所以这里需要记录父节点，方便后面继续托孤//同时，这里parent不能初始化为空，因为cur->_right可能直接就为右子树的最左节点，此时不会进循环，parent也不会被赋值Node* parent = cur;while (minRight->_left)  //左为空即为最左节点{parent = minRight;minRight = minRight->_left;}//替换minRight和cur节点的值(直接将minRight值赋给cur就行，因为minRight最终会被释放掉)cur->_key = minRight->_key;//minRight可能是父的左节点，也可能是父的右节点，所以这里还需要判断//当cur->_right == minRight时，minRight托孤给父节点的右if (parent->_left == minRight)parent->_left = minRight->_right;else parent->_right = minRight->_right;delete minRight;}return true;}}//找不到返回falsereturn false;}//删除递归版本bool eraseR(const K& key) {return _eraseR(_root, key);}//中序遍历--用户在类外无法访问_root，所以我们可以再类内通过调用子函数的方法来实现遍历void InOrder() {_InOrder(_root);}private:void destory(Node* root) {if (root == nullptr)return;destory(root->_left);destory(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;}void _InOrder(Node* root) {if (root == nullptr)return;_InOrder(root->_left);std::cout << root->_key << " ";_InOrder(root->_right);}//插入递归版本//为了解决父节点无法链接子节点的问题，我们这里把root定义实参的引用bool _insertR(Node*& root, const K& key) {if (root == nullptr) {root = new Node(key);return true;}if (key > root->_key)return _insertR(root->_right, key);else if (key < root->_key)return _insertR(root->_left, key);elsereturn false;}//查找递归版本bool _findR(Node* root, const K& key) {if (root == nullptr)return false;if (key > root->_key)return _findR(root->_right, key);else if (key < root->_key)return _findR(root->_left, key);elsereturn true;}//删除递归版本//为了解决父节点链接的问题，这里还是使用引用--巧用引用bool _eraseR(Node*& root, const K& key) {if (root == nullptr)return false;if (key > root->_key)return _eraseR(root->_right, key);else if (key < root->_key)return _eraseR(root->_left, key);else  //删除{Node* del = root;//由于root是实参的别名，所以这里的root本来就是父节点的左孩子或右孩子//所以我们直接用root的left/right覆盖原来的root就自动链接上了，而不用再去找父节点//并且这里也适用于root为根的情况，不用单独处理if (root->_left == nullptr)  //左为空root = root->_right;else if (root->_right == nullptr)  //右为空root = root->_left;else  //左右都不为空{//找右子树最小节点进行替换Node* minRight = root->_right;while (minRight->_left) {minRight = minRight->_left;}//交换root和minRight的值std::swap(root->_key, minRight->_key);//此时key成为了右子树的最小节点，所以key的左子树一定为空，满足情况1//所以我们就可以让右子树第一个节点做根，然后到右子树中去递归删除key，复用前面的代码//此处不能传递minRight，因为minRight是一个局部变量，形参以它为别名无意义return _eraseR(root->_right, key);}delete del;return true;}}private:Node* _root;
};

Test.cpp：

#define _CRT_SECURE_NO_WARNINGS 1#include <iostream>
#include "BSTree.h"
using namespace std;//非递归版本
//void BSTreeTest1() {
//	BSTree<int> t;
//	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
//
//	for (auto e : a)
//		t.insert(e);
//	t.InOrder();
//	cout << endl;
//
//	t.erase(3);
//	t.InOrder();
//	cout << endl;
//
//	t.erase(8);
//	t.InOrder();
//	cout << endl;
//
//	for (auto e : a) {
//		t.erase(e);
//		t.InOrder();
//		cout << endl;
//	}
//}//递归版本
void BSTreeTest2() {BSTree<int> t;int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };for (auto e : a)t.insertR(e);t.InOrder();cout << endl;cout << t.findR(10) << endl;cout << t.findR(5) << endl;t.eraseR(3);t.InOrder();cout << endl;t.eraseR(8);t.InOrder();cout << endl;for (auto e : a) {t.eraseR(e);t.InOrder();cout << endl;}
}//默认成员函数
void BSTreeTest3() {BSTree<int> t1;int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };for (auto e : a)t1.insert(e);t1.InOrder();cout << endl;BSTree<int> t2 = t1;t2.InOrder();cout << endl;BSTree<int> t3;t3.insert(15);t3 = t2;t3.InOrder();cout << endl;
}int main() {BSTreeTest3();return 0;
}

四、二叉搜索树的应用

二叉搜索树主要应用于两种模型 – K 模型和 KV模型，我们上面实现的就是K模型。

K模型

K 模型即只有 key 作为关键码，结构中只需要存储 Key 即可，关键码即为需要搜索到的值，K 模型中，K 的值不可更改；下面我们以单词拼写来作为 K 模型的一个具体应用场景：

给一个单词word，判断该单词是否拼写正确 – 我们可以将 K 的类型定义为 string，然后将英语词库中的所有单词作为 key，构建一颗二叉搜索树，然后在二叉搜索树中对用户写出的每一个单词进行查找，如果找不到，则说明该单词拼写错误。

KV模型

KV 模型即在 K 模型的基础上，给每一个关键码 key 都对应上一个值 value，即<Key, Value>键值对，在 KV 模型中，K 的值不可更改，该 K 对应的 value 可以更改；KV 模型在日常生活中非常常见：

比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；

再比如统计每种类型水果的个数，统计成功后，给定水果类型就可快速找到该类型水果的个数，水果类型与其个数就是<fruit, count>就构成一种键值对。

下面我们尝试将我们之前的 K 模型代码简单改造为 KV 模型代码，并实现上面的音译汉和统计每种类型水果数量的功能：

//二叉搜索树--KV模型
namespace KV {template<class K, class V>struct BSTreeNode {BSTreeNode<K, V>* _left;BSTreeNode<K, V>* _right;K _key;V _value;BSTreeNode(const K& key = K(), const V& value = V()): _key(key), _value(value), _left(nullptr), _right(nullptr){}};template<class K, class V>class BSTree {typedef BSTreeNode<K, V> Node;public:BSTree(): _root(nullptr){}Node* find(const K& key) {Node* cur = _root;while (cur) {if (key > cur->_key)cur = cur->_right;else if (key < cur->_key)cur = cur->_left;elsereturn cur;}//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 (key > cur->_key) {  //比根大就往右子树放parent = cur;cur = cur->_right;}else if (key < cur->_key) {  //比根小往左放parent = cur;cur = cur->_left;}else {  //二叉搜索树中不允许有冗余节点，相等直接插入失败return false;}}//空位就是key的插入位置Node* newnode = new Node(key, value);if (key > parent->_key)parent->_right = newnode;else parent->_left = newnode;return true;}void InOrder() {_InOrder(_root);}private:void _InOrder(Node* root) {if (root == nullptr)return;_InOrder(root->_left);std::cout << root->_key << ":" << root->_value << " ";_InOrder(root->_right);}private:Node* _root;};
}

test.cpp1 – 英译汉：

void BSTree_KV_test1() {//英译汉KV::BSTree<string, string> dict;//输入<key,value>对，形成词库dict.insert("BinarryTree", "二叉树");dict.insert("SearchTree", "搜索树");dict.insert("English", "英语");dict.insert("Chinese", "汉语");dict.insert("Blog", "博客");//从词库中查找单词string str;while (cin >> str) {KV::BSTreeNode<string, string>* ret = dict.find(str);if (ret == nullptr)cout << "词库中不存在该单词" << endl;else {cout << ret->_value << endl;}}
}

test2 – 统计每种类型水果数量：

//统计不同类型水果数量
void BSTree_KV_test2() {string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };KV::BSTree<string, int> countTree;for (auto e : arr) {KV::BSTreeNode<string, int>* ret = countTree.find(e);if (ret == nullptr) {countTree.insert(e, 1);}else {ret->_value++;}}countTree.InOrder();
}

五、二叉树进阶面试题

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

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

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

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

5. 二叉搜索树与双向链表 牛客网 (nowcoder.com)

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

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

8. 144. 二叉树的前序遍历非递归迭代实现 - 力扣（LeetCode）

9. 94. 二叉树的中序遍历非递归迭代实现 - 力扣（LeetCode）

10. 145. 二叉树的后序遍历非递归迭代实现 - 力扣（LeetCode）