当前位置：首页 > web >正文

C++ 搜索二叉树（BST）详解：实现与应用

web 2025/6/23 19:07:57

一、搜索二叉树基础概念

二、BST节点结构实现

三、核心操作实现

1. 插入操作

2. 查找操作

3. 删除操作

四、BST的高级功能

1. 中序遍历

2. 拷贝构造函数和赋值运算符

3. 析构函数

五、键值对BST的实现

1. 字典应用

2. 统计应用

总结

搜索二叉树（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();
}