目录
搜索二叉树（Binary Search Tree, BST）是一种重要的数据结构，它结合了链表的灵活性和数组的快速查找优势。本文将详细介绍C++中搜索二叉树的实现原理、核心操作以及实际应用场景。
一、搜索二叉树基础概念
搜索二叉树是一种特殊的二叉树，它具有以下性质：
- 每个节点包含一个键值（key）
- 左子树所有节点的键值小于根节点的键值
- 右子树所有节点的键值大于根节点的键值
- 左右子树也分别是搜索二叉树
这种结构使得查找、插入和删除操作的平均时间复杂度为O(log n)。
二、BST节点结构实现
我们首先定义BST的节点结构：
template<class K>
class BSTreeNode {
public:
K _key; // 节点存储的键值
BSTreeNode<K>* _left; // 左子节点指针
BSTreeNode<K>* _right; // 右子节点指针
BSTreeNode(const K& key)
:_key(key)
,_left(nullptr)
,_right(nullptr)
{}
};
三、核心操作实现
1. 插入操作
非递归实现：
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 _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; // 键值已存在
}
}
2. 查找操作
非递归实现：
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 _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;
}
}
3. 删除操作
删除操作较为复杂，需要考虑三种情况：
- 删除叶子节点
- 删除只有左子树或右子树的节点
- 删除有两个子树的节点
非递归实现：
bool Erase(const K& key) {
Node* cur = _root;
Node* parent = cur;
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 (parent->_right == cur) {
parent->_right = cur->_right;
}
else {
parent->_left = cur->_right;
}
}
}
else if (cur->_right == nullptr) {
// 右子树为空的情况
if (cur == _root) {
_root = cur->_left;
}
else {
if (parent->_left == cur) {
parent->_left = cur->_left;
}
else {
parent->_right = cur->_left;
}
}
}
else {
// 左右子树都不为空的情况
Node* parent = cur;
Node* leftMax = cur->_left;
while (leftMax->_right) {
parent = leftMax;
leftMax = leftMax->_right;
}
swap(cur->_key, leftMax->_key);
if (parent->_left == leftMax) {
parent->_left = leftMax->_left;
}
else {
parent->_right = leftMax->_left;
}
cur = leftMax;
}
delete cur;
return true;
}
}
return false;
}
递归实现：
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->_left == nullptr) {
root = root->_right;
}
else if (root->_right == nullptr) {
root = root->_left;
}
else {
Node* leftMax = root->_left;
while (leftMax->_right) {
leftMax = leftMax->_right;
}
swap(root->_key, leftMax->_key);
return _EraseR(root->_left, key);
}
delete del;
return true;
}
}
四、BST的高级功能
1. 中序遍历
中序遍历BST会得到一个有序的序列：
void _InOrder(Node* root) {
if (root == nullptr) {
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
2. 拷贝构造函数和赋值运算符
BSTree(const BSTree<K>& t) {
_root = Copy(t._root);
}
BSTree<K>& operator=(BSTree<K> t) {
swap(_root, t._root);
return *this;
}
Node* Copy(Node* root) {
if (root == nullptr) return nullptr;
Node* copyroot = new Node(root->_key);
copyroot->_left = Copy(root->_left);
copyroot->_right = Copy(root->_right);
return copyroot;
}
3. 析构函数
~BSTree() {
Destroy(_root);
}
void Destroy(Node*& root) {
if (root == nullptr) return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
root = nullptr;
}
五、键值对BST的实现
我们可以扩展BST以支持键值对存储：
template<class K, class V>
class BSTreeNode {
public:
K _key;
V _value;
BSTreeNode<K,V>* _left;
BSTreeNode<K,V>* _right;
BSTreeNode(const K& key, const V& value)
:_key(key)
,_value(value)
,_left(nullptr)
,_right(nullptr)
{}
};
这种结构非常适合实现字典或统计应用：
1. 字典应用
void TestBSTree1() {
BSTree<string, string> dict;
dict.InsertR("insert", "插入");
dict.InsertR("sort", "排序");
dict.InsertR("right", "右边");
dict.InsertR("date", "日期");
string str;
while (cin >> str) {
auto ret = dict.FindR(str);
if (ret) {
cout << ret->_value << endl;
}
else {
cout << "无此单词" << endl;
}
}
}
2. 统计应用
void TestBSTree2() {
string arr[] = { "苹果","西瓜","西瓜","西瓜","香蕉","苹果", "苹果", "苹果", "苹果", "苹果" };
BSTree<string, int> countTree;
for (auto& str : arr) {
auto ret = countTree.FindR(str);
if (ret == nullptr) {
countTree.InsertR(str, 1);
}
else {
ret->_value++;
}
}
countTree.InOrder();
}
总结
搜索二叉树是数据结构与算法中的重要内容，掌握它的实现原理和应用场景对于提升编程能力非常有帮助。本文详细介绍了C++中BST的实现方法，包括基本操作和高级功能，并展示了它在实际中的应用。理解这些内容将为学习更复杂的数据结构打下坚实基础。
希望这篇博客对你理解和使用搜索二叉树有所帮助！如果有任何问题，欢迎在评论区留言讨论。