本文介绍 C++ 中二叉搜索树（BST）的概念、性质及基本操作。内容包括 BST 的定义、时间复杂度分析（最优 O(logN)，最坏 O(N)），以及查找、插入、删除三种核心操作的实现逻辑。文章详细阐述了 key 形式与 key_value 形式的 BST 模板实现，涵盖节点结构定义、递归遍历、内存管理（拷贝构造、析构）等细节，为后续学习平衡树及 STL 容器奠定基础。
二叉搜索树（Binary Search Tree，BST）：也称为二叉排序树或二叉查找树，是一种特殊的二叉树。二叉搜索树是一种高效的动态数据结构，用于存储有序数据，支持快速查找、插入和删除操作。二叉搜索树的核心特性是：通过二叉树结构维护元素的排序关系。
二叉搜索树具有以下特点和性质：
// 例如：下面这棵树就是一棵'二叉搜索树'
// 5
// / \
// 3 7
// / \ / \
// 2 4 6 8
二叉搜索树的效率和形态强相关：
显然，单支树形态的效率无法满足实际需求，因此后续会延伸讲解二叉搜索树的变形结构（平衡二叉搜索树），比如 AVL 树和红黑树——这类结构通过自平衡机制，能稳定维持树的高度在 log₂N 级别，更适合内存中数据的存储与搜索场景。
对比二分查找的缺陷： 虽然二分查找也能实现 O(log N) 级别的查找效率，但它存在两大核心缺陷：
- 存储结构限制：二分查找依赖支持下标随机访问的线性结构（如数组），且要求数据有序。
- 插入删除低效：在支持下标随机访问的结构中（如数组），插入/删除操作需要挪动大量数据（为保持有序性），时间复杂度会劣化到 O(N)，无法应对高频更新场景。
相比之下，平衡二叉搜索树既保留了二叉搜索树的有序性，又通过自平衡机制规避了单支树的低效问题，同时支持高效的插入、删除与查询，这正是其在工程实践中的核心价值。
查找操作利用二叉搜索树的特性：左子树的所有节点键值小于根节点，右子树的所有节点键值大于根节点，来进行不断地缩小搜索范围。正是这种'分治'思想使得二叉搜索树的查找操作无需遍历全树，大幅提高效率。
< 目标键 —> '往右子树继续找'。> 目标键 —> '往左子树继续找'。= 目标键 —> '找到了要查找的节点'。从根节点开始寻找指定 key 的节点：若目标值小于当前节点值，则在左子树中继续搜索；若目标值大于当前节点值，则在右子树中继续搜索；若相等，则找到了目标节点。 平均时间复杂度为 O(log n)，其中 n 是树中节点的数量。但在最坏情况下（如：树退化为链表），最坏时间复杂度会变为 O(n)。
向已有二叉搜索树中添加新节点的同时，且要维持其'左子树节点值 < 根节点值 < 右子树节点值'的特性。
< 要插入的键 —> '往右子树继续找'。> 要插入的键 —> '往左子树继续找'。= 要插入的键 —> '未找到要插入的位置'（键已存在）。先从根节点开始搜索插入位置：若目标值小于当前节点值，则向当前节点的左子树移动；若目标值大于当前节点值，则向当前节点的右子树移动；当到达叶子节点时，根据目标值与叶子节点值的大小关系，将新节点作为叶子节点的左子节点或右子节点插入。 平均时间复杂度为 O(log n)，最坏时间复杂度为 O(n)。
删除节点时需处理三种情况：
删除操作的核心目标是：删除节点后需要确保剩余节点仍满足二叉搜索树的性质：左子树所有节点键值 < 根节点 < 右子树所有节点键值。
若要删除的节点是叶子节点，直接删除即可；若节点只有一个子节点，将该节点的父节点与子节点直接连接，然后删除该节点；若节点有两个子节点，通常的做法是找到该节点右子树中的最小节点（即中序遍历下的后继节点），将其值赋给要删除的节点，然后删除该后继节点。 平均时间复杂度为 O(log n)，最坏情况为 O(n)。
在二叉搜索树的应用场景中，根据数据存储与使用需求不同，存在两种常见的形式：
#pragma once
#include <iostream>
using namespace std;
namespace key {
template<class K>
struct BSTNode {
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;
BSTNode(const K& key) : _key(key), _left(nullptr), _right(nullptr) {}
};
template<class K>
class BST {
public:
using Node = BSTNode<K>;
void InOrder() {
_InOrder(_root);
cout << endl;
}
bool Find(const K& key) {
Node* curr = _root;
while (curr) {
if (curr->_key < key) {
curr = curr->_right;
} else if (curr->_key > key) {
curr = curr->_left;
} else {
return true;
}
}
return false;
}
bool Insert(const K& key) {
if (_root == nullptr) {
_root = new Node(key);
return true;
}
Node* current = _root;
Node* parent = nullptr;
while (current) {
if (current->_key < key) {
parent = current;
current = current->_right;
} else if (current->_key > key) {
parent = current;
current = current->_left;
} else {
return false;
}
}
current = new Node(key);
if (key < parent->_key) {
parent->_left = current;
} else {
parent->_right = current;
}
return true;
}
bool Erase(const K& key) {
if (_root == nullptr) {
return false;
}
Node* current = _root;
Node* parent = nullptr;
while (current) {
if (current->_key < key) {
parent = current;
current = current->_right;
} else if (current->_key > key) {
parent = current;
current = current->_left;
} else {
if (current->_left == nullptr) {
if (current == _root) {
_root = current->_right;
} else {
if (parent->_left == current) {
parent->_left = current->_right;
} else {
parent->_right = current->_right;
}
}
delete current;
} else if (current->_right == nullptr) {
if (current == _root) {
_root = current->_left;
} else {
if (parent->_left == current) {
parent->_left = current->_left;
} else {
parent->_right = current->_left;
}
}
delete current;
} else {
Node* replace = current->_right;
Node* replaceParent = current;
while (replace->_left) {
replaceParent = replace;
replace = replace->_left;
}
current->_key = replace->_key;
if (replace == replaceParent->_left) {
replaceParent->_left = replace->_right;
} else {
replaceParent->_right = replace->_right;
}
delete replace;
}
return true;
}
}
return false;
}
private:
Node* _root = nullptr;
void _InOrder(Node* root) {
if (root == nullptr) {
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
};
}
#define _CRT_SECURE_NO_WARNINGS 1
#include "BinarySearchTree.h"
#include <iostream>
using namespace std;
void Test01() {
cout << "===== 测试基本功能 =====" << endl;
key::BST<int> bst;
int arr[] = { 50, 30, 70, 20, 40, 60, 80 };
cout << "插入数据：";
for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i) {
cout << arr[i] << " ";
bst.Insert(arr[i]);
}
cout << endl;
cout << "中序遍历结果 (应有序): ";
bst.InOrder();
cout << "查找存在的元素 50: " << (bst.Find(50) ? "存在" : "不存在") << endl;
cout << "查找不存在的元素 90: " << (bst.Find(90) ? "存在" : "不存在") << endl;
}
void Test02() {
cout << "\n===== 测试删除操作 =====" << endl;
key::BST<int> bst;
int arr[] = { 50, 30, 70, 20, 40, 60, 80 };
for (int val : arr) {
bst.Insert(val);
}
cout << "原始树中序遍历：";
bst.InOrder();
cout << "删除叶子节点 20 后：";
bst.Erase(20);
bst.InOrder();
cout << "删除只有右子树的节点 30 后：";
bst.Erase(30);
bst.InOrder();
cout << "删除只有左子树的节点 70 后：";
bst.Erase(70);
bst.InOrder();
cout << "删除有左右子树的节点 50 后：";
bst.Erase(50);
bst.InOrder();
}
int main() {
Test01();
Test02();
return 0;
}
#pragma once
#include <iostream>
using namespace std;
namespace key_value {
template<class K, class V>
struct BSTNode {
K _key;
V _value;
BSTNode<K, V>* _left;
BSTNode<K, V>* _right;
BSTNode(const K& key, const V& value) : _key(key), _value(value), _left(nullptr), _right(nullptr) {}
};
template<class K, class V>
class BST {
public:
using Node = BSTNode<K, V>;
BST() = default;
BST(const BST& t) {
_root = Copy(t._root);
}
BST& operator=(BST tmp) {
swap(_root, tmp._root);
return *this;
}
~BST() {
Destroy(_root);
_root = nullptr;
}
Node* Find(const K& key) {
Node* curr = _root;
while (curr) {
if (curr->_key < key) {
curr = curr->_right;
} else if (curr->_key > key) {
curr = curr->_left;
} else {
return curr;
}
}
return nullptr;
}
bool Insert(const K& key, const V& value) {
if (_root == nullptr) {
_root = new Node(key, value);
return true;
}
Node* current = _root;
Node* parent = nullptr;
while (current) {
if (current->_key < key) {
parent = current;
current = current->_right;
} else if (current->_key > key) {
parent = current;
current = current->_left;
} else {
return false;
}
}
current = new Node(key, value);
if (key < parent->_key) {
parent->_left = current;
} else {
parent->_right = current;
}
return true;
}
bool Erase(const K& key) {
if (_root == nullptr) {
return false;
}
Node* current = _root;
Node* parent = nullptr;
while (current) {
if (current->_key < key) {
parent = current;
current = current->_right;
} else if (current->_key > key) {
parent = current;
current = current->_left;
} else {
if (current->_left == nullptr) {
if (current == _root) {
_root = current->_right;
} else {
if (parent->_left == current) {
parent->_left = current->_right;
} else {
parent->_right = current->_right;
}
}
delete current;
} else if (current->_right == nullptr) {
if (current == _root) {
_root = current->_left;
} else {
if (parent->_left == current) {
parent->_left = current->_left;
} else {
parent->_right = current->_left;
}
}
delete current;
} else {
Node* replace = current->_right;
Node* replaceParent = current;
while (replace->_left) {
replaceParent = replace;
replace = replace->_left;
}
current->_key = replace->_key;
if (replace == replaceParent->_left) {
replaceParent->_left = replace->_right;
} else {
replaceParent->_right = replace->_right;
}
delete replace;
}
return true;
}
}
return false;
}
void InOrder() {
_InOrder(_root);
cout << endl;
}
private:
Node* _root = nullptr;
void _InOrder(Node* root) {
if (root == nullptr) {
return;
}
_InOrder(root->_left);
cout << root->_key << ":" << root->_value << endl;
_InOrder(root->_right);
}
Node* Copy(const Node* root) {
if (root == nullptr) {
return nullptr;
}
Node* newRoot = new Node(root->_key, root->_value);
newRoot->_left = Copy(root->_left);
newRoot->_right = Copy(root->_right);
return newRoot;
}
void Destroy(Node* root) {
if (root == nullptr) {
return;
}
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
};
}
#define _CRT_SECURE_NO_WARNINGS 1
#include "BinarySearchTree.h"
#include <iostream>
using namespace std;
void Test01() {
cout << "========= 测试基本功能 =========" << endl;
key_value::BST<string, string> dict;
dict.Insert("apple", "苹果");
dict.Insert("banana", "香蕉");
dict.Insert("cherry", "樱桃");
dict.Insert("date", "枣");
cout << "插入后的中序遍历（按键排序）：" << endl;
dict.InOrder();
auto node = dict.Find("banana");
if (node) cout << "查找 'banana' 成功，值为：" << node->_value << endl;
else cout << "查找 'banana' 失败" << endl;
node = dict.Find("grape");
if (node) cout << "查找 'grape' 成功，值为：" << node->_value << endl;
else cout << "查找 'grape' 失败（预期结果）" << endl;
}
void Test02() {
cout << "\n========= 测试删除操作 =========" << endl;
key_value::BST<int, string> bst;
bst.Insert(50, "五十");
bst.Insert(30, "三十");
bst.Insert(70, "七十");
bst.Insert(20, "二十");
bst.Insert(40, "四十");
bst.Insert(60, "六十");
bst.Insert(80, "八十");
cout << "原始树中序遍历：" << endl;
bst.InOrder();
cout << "删除叶子节点 20 后：" << endl;
bst.Erase(20);
bst.InOrder();
cout << "删除只有右子树的节点 30 后：" << endl;
bst.Erase(30);
bst.InOrder();
cout << "删除只有左子树的节点 70 后：" << endl;
bst.Erase(70);
bst.InOrder();
cout << "删除有左右子树的节点 50 后：" << endl;
bst.Erase(50);
bst.InOrder();
cout << "删除根节点 40 后：" << endl;
bst.Erase(40);
bst.InOrder();
}
void Test03() {
cout << "\n========= 测试拷贝构造和赋值运算符 =========" << endl;
key_value::BST<string, int> original;
original.Insert("张三", 18);
original.Insert("李四", 20);
original.Insert("王五", 22);
original.Insert("赵六", 24);
cout << "原始树中序遍历：" << endl;
original.InOrder();
cout << "\n--------测试拷贝构造--------" << endl;
key_value::BST<string, int> copy1(original);
cout << "拷贝构造后的树中序遍历：" << endl;
copy1.InOrder();
cout << "\n--------测试赋值运算符--------" << endl;
key_value::BST<string, int> copy2;
copy2 = original;
cout << "赋值运算符后的树中序遍历：" << endl;
copy2.InOrder();
cout << "\n--------修改原树，验证深拷贝--------" << endl;
original.Insert("钱七", 26);
cout << "修改原树后，原树中序遍历：" << endl;
original.InOrder();
cout << "拷贝树中序遍历（应不受影响）：" << endl;
copy1.InOrder();
}
int main() {
Test01();
Test02();
Test03();
return 0;
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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