C++算法
C++ 搜索二叉树：特性、实现与应用
C++ 搜索二叉树（BST）是一种特殊的二叉树，左子树节点值小于根节点，右子树大于等于根节点。文章详细讲解了 BST 的概念、核心特性及时间复杂度分析，对比了二分查找的局限性。重点实现了插入、查找、删除操作的 C++ 代码，包括处理左右子树为空及非空的删除逻辑。最后探讨了 Key 和 Key/Value 两种使用场景，如车牌识别、单词统计等，并提供了完整的类定义与测试用例。
C++ 搜索二叉树（BST）是一种特殊的二叉树，左子树节点值小于根节点，右子树大于等于根节点。文章详细讲解了 BST 的概念、核心特性及时间复杂度分析，对比了二分查找的局限性。重点实现了插入、查找、删除操作的 C++ 代码，包括处理左右子树为空及非空的删除逻辑。最后探讨了 Key 和 Key/Value 两种使用场景，如车牌识别、单词统计等，并提供了完整的类定义与测试用例。
BST 支持动态数据集合的高效操作，适合频繁插入、删除和查找的场景。
利用二叉树的分支特性，BST 在平均情况下能实现 O(logN) 的搜索效率。
注意：时间复杂度指的是最差情况下，所以时间复杂度为 O(N)。
最差情况如图：
那么这样的效率显然是无法满足我们需求的，因此后面会介绍二叉搜索树的变形——平衡二叉搜索树 AVL 树和红黑树，才能适用于我们在内存中存储和搜索数据。
另外需要说明的是，二分查找也可以实现 O(logN) 级别的查找效率，但是二分查找有两大缺陷：
如右图所示：数据越有序，插入结果越坏——高度高、递归深、效率低。 如左图所示：插入越无序的数据，左右会平衡一点，结果反而越好。
二叉搜索树常简写为 BST，提高代码可读性。二叉搜索树也叫搜索二叉树。
template<class K> struct BSTreeNode {
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
BSTreeNode(const K& key) :_left(nullptr), _right(nullptr), _key(key) { }
};
提供插入、查找、删除等基本操作的接口设计如下：
从根节点开始，根据键值大小选择左子树或右子树，直到找到空位置插入新节点。
插入分成以下三种情况：
提示：我们就以下面这张图为搜索二叉树来进行实践。
我们定义这样一个数组：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;
}
private:
Node* _root = nullptr;
};
我们在 Test.cpp 文件里面包一下头文件，给一个数组，再定义出一棵树，因为数组也是支持范围 for 的，这里我们用范围 for 把数据插入进去。
C++ 递归很麻烦，这里要传根，但是根是私有的。调的是不需要传根的，再去调用这个子函数，把根传过去，这样外面就不需要传了，也不需要提供 get root，不过 get root 调用的时候也方便。
利用 BST 的中序遍历必然有序的特性验证插入正确性。
思考：这里为什么要使用中序遍历验证呢？
中序遍历的好处：中序遍历：最简单的递归中序遍历有序，并且数据都在，并且能够很好地验证功能。验证搜索二叉树只需判断中序遍历是否为递增即可。
成功插入进去了，并且因为是中序遍历，结果是有序的。
利用 BST 的排序特性，通过比较键值快速定位目标节点。
查找的代码也可以递归写，也可以不用。
我们就查找一下 1 这个数据。
首先需要找到待删除节点及其父节点。
首先查找元素是否在二叉搜索树中，如果不存在，则返回 false。
如果查找元素存在则分以下四种情况需要分别处理一下（假设要删除的结点为 N）：
接下来我们通过具体例子来看看各种删除情况。
实现高效的节点查找逻辑。
// 搜索二叉树这个部分，删除是很麻烦的，先找到再删除，找到不难，但是删除很难
// 面试如果考，一定不会考插入、查找，肯定会考删除
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 == _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
}
这里是删 8 是会出问题的！我们要改一改。
改变根节点，让这个孩子自己变成根。
需要全部再删一次，重复删不会报错。
运行一下。
//不好听
//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; // 从根节点开始搜索
// 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 == _root) // 如果要删除的是根节点，（改变根节点）让孩子自己变成根
{
_root = cur->_right; // 上面是左为空，所以让父亲指向我的右，让右孩子成为新的根
}
else
{
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 InOrder() // 套一层，因为外面拿不到跟，里面可以
{
_InOrder(_root);
cout << endl;
}
private:
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 {
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 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;
};
}
#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 即可，关键码即为需要搜索到的值，搜索场景只需要判断 Key 在不在。Key 的搜索场景实现的二叉搜索树支持增删查，但是不支持修改，修改 Key 破坏搜索树结构了。
场景 1：小区无人值守车库，小区车库买了车位的业主车才能进小区，那么物业会把买了车位的业主的车牌号录入后台系统，车辆进入时扫描车牌在不在系统中，在则抬杆，不在则提示非本小区车辆，无法进入。
场景 2：检查一篇英文文章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中的单词，查找是否在二叉搜索树中，不在则波浪线标红提示。
每一个关键码 Key，都有与之对应的值 Value，Value 可以任意类型对象。树的结构中（结点）除了需要存储 Key 还要存储对应的 Value，增/删/查还是以 Key 为关键字走二叉搜索树的规则进行比较，可以快速查找到 Key 对应的 Value。Key/Value 的搜索场景实现的二叉搜索树支持修改，但是不支持修改 Key，修改 Key 破坏搜索树性质了，可以修改 Value。
场景 1：简单中英互译字典，树的结构中（结点）存储 Key(英文）和 Value（中文），搜索时输入英文，则同时查找到了英文对应的中文。
场景 2：商场无人值守车库，入口进场时扫描车牌，记录车牌和入场时间，出口离场时，扫描车牌，查找入场时间，用当前时间 - 入场时间计算出停车时长，计算出停车费用，缴费后抬杆，车辆离场。
场景 3：统计一篇文章中单词出现的次数，读取一个单词，查找单词是否存在，不存在这个说明第一次出现，( 单词 , 1），单词存在，则++单词对应的次数。
Key / Value 场景下的代码实现如下所示（见上文 namespace key_value 部分）。
运行一下。
^Z：Ctrl + Z + Enter（回车），就能取消运行。
结语：搜索二叉树（BST）的价值，恰在于它用'左小右大'的简单规则，搭建起了'高效查找'与'有序数据'之间的桥梁 —— 从图解中清晰可见的层级结构，到代码里递归实现的插入、删除逻辑，每一处设计都围绕着'平衡效率与规则'的核心目标。它既是二叉树特性的具象化应用，也是理解复杂平衡树（如 AVL、红黑树）的'入门钥匙'，那些看似抽象的'中序遍历有序性''节点删除场景分类'，通过图解的可视化呈现，都能转化为可感知、可验证的逻辑。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online