《C++ 搜索二叉树》深入理解 C++ 搜索二叉树：特性、实现与应用

在 C++ 数据结构体系中，搜索二叉树（Binary Search Tree，简称 BST）是连接 “线性结构” 与 “高级树结构” 的关键桥梁。它既保留了二叉树的层级特性，又通过严格的节点值规则实现高效的查找、插入与删除操作，是后续学习 AVL 树、红黑树、B + 树等平衡树的基础。无论是日常开发中的动态数据查找，还是数据库索引、缓存系统的底层设计，BST 的思想都无处不在。本文将以 C++ 为载体，从概念定义到代码实现，逐步拆解 BST 的核心逻辑，帮助读者掌握其本质与实践技巧

一、理解二叉搜索树

1.1 二叉搜索树的概念

若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值；
若它的右子树不为空，则右子树上所有结点的值都大于等于根结点的值；
它的左右子树也分别为二叉搜索树；
二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义

如下图所示就是两个搜索二叉树

1.2 核心特性

1.2.1 多元化的结构：灵活的数据结构

BST支持动态数据集合的高效操作，适合频繁插入、删除和查找的场景

1.2.2 天然的搜索优势：擅长搜索的数据结构

利用二叉树的分支特性，BST在平均情况下能实现O(logn)的搜索效率

二、二叉搜索树性能分析

2.1 时间复杂度分析

最优情况下，二叉搜索树为完全二叉树（或者接近完全二叉树），其高度为：logN；
最差情况下，二叉搜索树退化为单支树（或者类似单支），其高度为：N；

注意：时间复杂度指的是最差情况下，所以时间复杂度为O(N)

最差情况如图：

那么这样的效率显然是无法满足我们需求的，因此后面博主会介绍二叉搜索树的变形——平衡二叉搜索树AVL树和红黑树，才能适用于我们在内存中存储和搜索数据

2.2 二分查找的局限性

另外需要说明的是，二分查找也可以实现O(logN)级别的查找效率，但是二分查找有两大缺陷

需要存储在支持下标随机访问的结构中，并且有序
插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据

如右图所示：数据越有序，插入结果越坏——高度高、递归深、效率低

如左图所示：插入越无序的数据，左右会平衡一点，结果反而越好

三、实现二叉搜索树的定义

3.1 命名规范

二叉搜索树常简写为BST，提高代码可读性（SBT不好听），二叉搜索树也叫搜索二叉树

3.2 定义节点

template<class K> struct BSTreeNode { BSTreeNode<K>* _left; BSTreeNode<K>* _right; K _key; BSTreeNode(const K& key) :_left(nullptr) , _right(nullptr) , _key(key) { } };

3.3 实践：完整的类定义

提供插入、查找、删除等基本操作的接口设计如下：

四、二叉树搜索的插入操作详解

4.1 插入算法流程

从根节点开始，根据键值大小选择左子树或右子树，直到找到空位置插入新节点。

插入分成以下三种情况：

树为空，则直接新增结点，赋值给root指针
树不空，按二叉搜索树性质，插入值比当前结点大就往右走，插入值比当前结点小就往左走，找到空位置，插入新结点
如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点（要注意保持逻辑一致性，插入相等的值不要一会往右走，一会又往左走）

提示：我们就以下面这张图为搜素二叉树来进行实践

4.2 代码实践

4.2.1 代码演示

我们定义这样一个数组

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

代码如下（不允许相等的值输入）：

//不允许相等的值插入 template<class K> class BSTree { typedef BSTreeNode<K> Node; public: 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; } }

4.2.2 测试用例设计

我们在Test.cpp文件里面包一下头文件，给一个数组，再定义出一棵树，因为数组也是支持范围for的，这里我们用范围for把数据插入进去

4.2.3 C++递归的麻烦之处

C++递归很麻烦，这里要传根，但是根是私有的

调的是不需要传根的，再去调用这个子函数，把根传过去，这样外面就不需要传了，也不需要提供get root，不过get root调用的时候也方便

4.3 InOrder：中序遍历验证

利用BST的中序遍历必然有序的特性验证插入正确性。

要写成这样套一层的结构，原因上面已经提到了，这里不再赘述

思考：这里为什么要使用中序遍历验证呢？

中序遍历的好处：中序遍历：最简单的递归中序遍历有序，并且数据都在，并且能够很好地验证功能验证搜索二叉树只需判断中序遍历是否为递增即可

4.4 运行演示

成功插入进去了，并且因为是中序遍历，结果是有序的

五、查找操作实现

5.1 查找算法

利用BST的排序特性，通过比较键值快速定位目标节点

从根开始比较，查找x，x比根的值大则往右边走查找，x比根值小则往左边走查找
最多查找高度次，走到到空，还没找到，这个值不存在
如果不支持插入相等的值，找到x即可返回
如果支持插入相等的值，意味着有多个x存在，一般要求查找中序的第一个x。如下图，查找3，要找到1的右孩子的那个3返回

5.2 代码实践

查找的代码也可以递归写，也可以不用

5.3 测试用例设计

我们就查找一下1这个数据

5.4 运行

六、删除操作深度解析

6.1 删除前的定位：要先查找一下

首先需要找到待删除节点及其父节点

6.1.1 查找元素存在分四种情况

首先查找元素是否在二又搜索树中，如果不存在，则返回false。

如果查找元素存在则分以下四种情况需要分别处理一下（假设要删除的结点为N）

要删除结点N左右孩子均为空
要删除的结点N左孩子位空，右孩子结点不为空
要删除的结点N右孩子位空，左孩子结点不为空
要删除的结点N左右孩子结点均不为空

6.1.2 对应以上四种情况的解决方案

把N结点的父亲对应孩子指针指向空，直接删除N结点（情况1可以当成2或者3进行处理，效果是一样的）
把N结点的父亲对应孩子指针指向N的右孩子，直接删除N结点
把N结点的父亲对应孩子指针指向N的左孩子，直接删除N结点
无法直接删除N结点，因为N的两个孩子无处安放，只能用替换法删除。找N左子树的值最大结点R（最右结点）或者N右子树的值最小结点R（最左结点）替代N，因为这两个结点中任意一个，放到N的位置，都满足二叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换，转而变成删除R结点，R结点符合情况2或情况3，可以直接删除

6.2 示例分析

接下来我们通过具体例子来看看各种删除情况

6.3 实践：代码实现

6.3.1 节点定位：查找要删除的节点

实现高效的节点查找逻辑

6.3.2 左子树为空的情况

6.3.3 右子树为空的情况

6.3.4 左右子树都存在的情况

6.3.5 完整的Erase实现

 // 搜索二叉树这个部分，删除是很麻烦的，先找到再删除，找到不难，但是删除很难 // 面试如果考，一定不会考插入、查找，肯定会考删除 bool Erase(const K& key) { Node* parent = nullptr; // 记录当前节点的父节点 Node* cur = _root; // 从根节点开始搜索 // 1、查找要删除的节点 while (cur) { if (cur->_key < key) // 目标key比当前节点大，向右子树搜索 { parent = cur; cur = cur->_right; } else if (cur->_key > key) // 目标key比当前节点小，向左子树搜索 { parent = cur; cur = cur->_left; } else // 找到要删除的节点cur——要干掉的节点 { // 情况1：要删除的节点左子树为空（只有右子树或没有子树） // 左为空 if (cur->_left == nullptr) // 父亲节点的左指向我的右 { //if (cur == parent->_left) // 13没删掉 if (cur == _root) // 如果要删除的是根节点,（改变根节点）让孩子自己变成根 { _root = cur->_right; // 上面是左为空，所以让父亲指向我的右 // 让右孩子成为新的根 } else { // 判断cur是父节点的左孩子还是右孩子 if (cur == parent->_left) // 父亲节点的左指向我的右，父节点的左指针指向cur的右孩子 { parent->_left = cur->_right; } else // 父亲节点的右指向我的左 { parent->_right = cur->_right; // 父节点的右指针指向cur的右孩子 } } delete cur; // 删除cur，释放节点内存 return true; // 找到了，删除成功 } // 情况2：要删除的节点右子树为空（只有左子树） // 右为空 else if (cur->_right == nullptr) // 父亲节点的右指向我的左 { if (cur == _root) // 如果要删除的是根节点，（改变根节点）让孩子自己变成根 { _root = cur->_left; // 上面是右为空，所以让父亲指向我的左 // 让左孩子成为新的根 } else { if (cur == parent->_left) { parent->_left = cur->_left; // 父节点的左指针指向cur的左孩子 } else { parent->_right = cur->_left; // 父节点的右指针指向cur的左孩子 } } delete cur; // 释放节点内存 return true; // 删除成功 } // 情况3：要删除的节点左右子树都不为空（最复杂的情况！！！） else // 左右均不为空 { // 策略：用右子树的最小节点（中序后继）来替代当前节点 // 找cur右子树的最小节点替代 Node* replaceParent = cur; // 替代节点的父节点，replace节点的parent，没有这个就不好删 Node* replace = cur->_right; // 从右子树开始找 // 在右子树中一直向左找，找到最小的节点（最左节点） while (replace->_left) // 找最左节点，不为空就继续，等于空就找到了 { replaceParent = replace; // 把replace给过去，每次都给 replace = replace->_left; // 左不为空，就不断往左边找 } // 用替代节点的值覆盖要删除节点的值 cur->_key = replace->_key; // 不需要交换，替代的本质是把replace节点的值传过去 // 需要判断一下 // 删除替代节点（替代节点要么是叶子节点，要么只有右子树） if (replaceParent->_left == replace) // 如果左指向replace replaceParent->_left = replace->_right; // 连接替代节点的右子树,让左指向replace的右 else // 如果右指向replace replaceParent->_right = replace->_right; // 连接替代节点的右子树，让右指向replace的右 delete replace; // 释放替代节点内存，彻底删除replace return true; // 删除成功 } } } return false; // 没找到删除的节点，直接return false }

6.4 测试用例设计

这里是删8是会出问题的！我们要改一改。

6.4.1 替代节点的父节点就是当前节点：replace的parent就是cur

6.4.2 需要判断一下：连接判断逻辑

改变根节点，让这个孩子自己变成根

6.5 访问for重新删

需要全部再删一次，重复删不会报错。

6.6 运行

运行一下

七、二叉搜索树的完整代码示例与实践演示

SearchBinaryTree.h：

//不好听 //struct SearchBinaryTree //struct SBTreeNode namespace key { template<class K> struct BSTreeNode { BSTreeNode<K>* _left; BSTreeNode<K>* _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 == 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 // { // //删除cur // 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 // { // // 找cur右子树的最小节点替代 // Node* replaceParent = cur; // Node* replace = cur->_right; // while (replace->_left) // { // replaceParent = replace; // replace = replace->_left; // } // cur->_key = replace->_key; // if (replaceParent->_left == replace) // replaceParent->_left = replace->_right; // else // replaceParent->_right = replace->_right; // delete cur; // return true; // } // } // } // return false; //} // 搜索二叉树这个部分，删除是很麻烦的，先找到再删除，找到不难，但是删除很难 // 面试如果考，一定不会考插入、查找，肯定会考删除 bool Erase(const K& key) { Node* parent = nullptr; // 记录当前节点的父节点 Node* cur = _root; // 从根节点开始搜索 // 1、查找要删除的节点 while (cur) { if (cur->_key < key) // 目标key比当前节点大，向右子树搜索 { parent = cur; cur = cur->_right; } else if (cur->_key > key) // 目标key比当前节点小，向左子树搜索 { parent = cur; cur = cur->_left; } else // 找到要删除的节点cur——要干掉的节点 { // 情况1：要删除的节点左子树为空（只有右子树或没有子树） // 左为空 if (cur->_left == nullptr) // 父亲节点的左指向我的右 { //if (cur == parent->_left) // 13没删掉 if (cur == _root) // 如果要删除的是根节点,（改变根节点）让孩子自己变成根 { _root = cur->_right; // 上面是左为空，所以让父亲指向我的右 // 让右孩子成为新的根 } else { // 判断cur是父节点的左孩子还是右孩子 if (cur == parent->_left) // 父亲节点的左指向我的右，父节点的左指针指向cur的右孩子 { parent->_left = cur->_right; } else // 父亲节点的右指向我的左 { parent->_right = cur->_right; // 父节点的右指针指向cur的右孩子 } } delete cur; // 删除cur，释放节点内存 return true; // 找到了，删除成功 } // 情况2：要删除的节点右子树为空（只有左子树） // 右为空 else if (cur->_right == nullptr) // 父亲节点的右指向我的左 { if (cur == _root) // 如果要删除的是根节点，（改变根节点）让孩子自己变成根 { _root = cur->_left; // 上面是右为空，所以让父亲指向我的左 // 让左孩子成为新的根 } else { if (cur == parent->_left) { parent->_left = cur->_left; // 父节点的左指针指向cur的左孩子 } else { parent->_right = cur->_left; // 父节点的右指针指向cur的左孩子 } } delete cur; // 释放节点内存 return true; // 删除成功 } // 情况3：要删除的节点左右子树都不为空（最复杂的情况！！！） else // 左右均不为空 { // 策略：用右子树的最小节点（中序后继）来替代当前节点 // 找cur右子树的最小节点替代 Node* replaceParent = cur; // 替代节点的父节点，replace节点的parent，没有这个就不好删 Node* replace = cur->_right; // 从右子树开始找 // 在右子树中一直向左找，找到最小的节点（最左节点） while (replace->_left) // 找最左节点，不为空就继续，等于空就找到了 { replaceParent = replace; // 把replace给过去，每次都给 replace = replace->_left; // 左不为空，就不断往左边找 } // 用替代节点的值覆盖要删除节点的值 cur->_key = replace->_key; // 不需要交换，替代的本质是把replace节点的值传过去 // 需要判断一下 // 删除替代节点（替代节点要么是叶子节点，要么只有右子树） if (replaceParent->_left == replace) // 如果左指向replace replaceParent->_left = replace->_right; // 连接替代节点的右子树,让左指向replace的右 else // 如果右指向replace replaceParent->_right = replace->_right; // 连接替代节点的右子树，让右指向replace的右 delete replace; // 释放替代节点内存，彻底删除replace return true; // 删除成功 } } } return false; // 没找到删除的节点，直接return false } //类里面的递归都要这样玩去，尤其是树的递归，因为树的递归传的都是根，都要套一层， void InOreder()//套一层，因为外面拿不到跟，里面可以， { _InOreder(_root); cout << endl; } private: void _InOreder(Node* root) { if (root == nullptr) return; _InOreder(root->_left);//先递归访问左子树，传左子树的根 cout << root->_key << ' ';//再看这个地方的值 _InOreder(root->_right);//再递归访问右子树，传右子树的根 } private: Node* _root = nullptr; }; } /////////////////////////////////////////////////////////////////////////////////////////// namespace key_value { template<class K,class V> struct BSTreeNode { BSTreeNode<K,V>* _left; BSTreeNode<K,V>* _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& val) { if (_root == nullptr) { _root = new Node(key,val); 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,val); 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 { // 删除cur 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 // 左右均不为空 { // 找cur右子树的最小节点替代 Node* replaceParent = cur; Node* replace = cur->_right; while (replace->_left) { replaceParent = replace; replace = replace->_left; } cur->_key = replace->_key; if (replaceParent->_left == replace) replaceParent->_left = replace->_right; else replaceParent->_right = replace->_right; delete replace; return true; } } } return false; } void InOreder() { _InOreder(_root); cout << endl; } private: void _InOreder(Node* root) { if (root == nullptr) return; _InOreder(root->_left); cout << root->_key << ': ' << root->_value << endl; _InOreder(root->_right); } private: Node* _root = nullptr; }; }

Test.cpp：

#define _CRT_SECURE_NO_WARNINGS 1 #include"SearchBinaryTree.h" int main() { int a[] = { 8,3,1,10,1,6,4,7,14,13 }; // 给一个数组 BSTree<int> t; // 定义一棵树 for (auto e : a) // 数组也支持访问for { t.Insert(e); // 把数据插入进去 } t.InOrder(); // C++递归很麻烦，这里要传根，但是根是私有的 // 打印结果：1 3 4 6 7 8 10 13 14（成功，并且是有序的——中序遍历） // 这样基本上说明插入是没问题的 t.Find(1); t.InOrder(); t.Erase(3); // 没啥问题 t.Erase(8); t.InOrder(); t.Erase(1); // 没啥问题 t.InOrder(); t.Erase(10); // 左为空 t.InOrder(); for (auto e : a) // 需要全部再删一次，重复删不会报错 { t.Insert(e); } return 0; }

运行演示

八、二叉搜索树key和key / value使用场景

只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值，搜索场景只需要判断key在不在。key的搜索场景实现的二又树搜索树支持增删查，但是不支持修改，修改key破坏搜索树结构了

场景1：小区无人值守车库，小区车库买了车位的业主车才能进小区，那么物业会把买了车位的业主的车牌号录入后台系统，车辆进入时扫描车牌在不在系统中，在则抬杆，不在则提示非本小区车辆，无法进入

场景2：检查一篇英文文章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中的单词，查找是否在二叉搜索树中，不在则波浪线标红提示

8.2 key / value使用场景

每一个关键码key，都有与之对应的值value，value可以任意类型对象。树的结构中（结点）除了需要存储key还要存储对应的value，增/删/查还是以key为关键字走二叉搜索树的规则进行比较，可以快速查找到key对应的value。key/value的搜索场景实现的二叉树搜索树支持修改，但是不支持修改key，修改key破坏搜索树性质了，可以修改value

场景1：简单中英互译字典，树的结构中（结点）存储key(英文）和vlaue（中文），搜索时输入英文，则同时查找到了英文对应的中文

场景2：商场无人值守车库，入口进场时扫描车牌，记录车牌和入场时间，出口离场时，扫描车牌，查找入场时间，用当前时间-入场时间计算出停车时长，计算出停车费用，缴费后抬杆，车辆离场

场景3：统计一篇文章中单词出现的次数，读取一个单词，查找单词是否存在，不存在这个说明第一次出现，( 单词 , 1），单词存在，则++单词对应的次数

8.3 实践：key / value代码实现

key / value场景下的代码实现如下所示

namespace key_value { template<class K,class V> struct BSTreeNode { BSTreeNode<K,V>* _left; BSTreeNode<K,V>* _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& val) { if (_root == nullptr) { _root = new Node(key,val); 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,val); 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 { // 删除cur 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 // 左右均不为空 { // 找cur右子树的最小节点替代 Node* replaceParent = cur; Node* replace = cur->_right; while (replace->_left) { replaceParent = replace; replace = replace->_left; } cur->_key = replace->_key; if (replaceParent->_left == replace) replaceParent->_left = replace->_right; else replaceParent->_right = replace->_right; delete replace; return true; } } } return false; } void InOreder() { _InOreder(_root); cout << endl; } private: void _InOreder(Node* root) { if (root == nullptr) return; _InOreder(root->_left); cout << root->_key << ': ' << root->_value << endl; _InOreder(root->_right); } private: Node* _root = nullptr; };

8.4 设计测试用例

8.4.1 测试用例

8.4.2 测试用例二

8.5 运行演示

8.5.1 测试用例一运行演示