C++ 二叉搜索树：从基础概念到代码实现

二叉搜索树（BST）是一种特殊的二叉树，左子节点值小于根节点，右子节点值大于根节点。其平均时间复杂度为 O(logN)，最坏为 O(N)。文章详细讲解了 BST 的概念、性能分析、插入、查找、删除操作及核心区别总结。提供了仅 Key 和 Key/Value 对的 C++ 代码实现，并分析了在集合、映射、缓存等场景下的应用选择。

涅槃凤凰发布于 2026/2/70 浏览

1. 二叉搜索树的概念

二叉搜索树又称二叉排序树，它要么是一棵空树，要么是具有以下性质的二叉树：

若它的左子树不为空，则左子树上所有节点的值都小于根结点的值。
若它的右子树不为空，则右子树上所有节点的值都大于根结点的值。
它的左右子树分别为二叉搜索树。
二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体要看使用场景的定义。map/set/multimap/multiset系列容器底层就是二叉搜索树，其中 map/set 不支持插入相等值，multimap/multiset 支持插入相等值。

2. 二叉搜索树的性能分析

最优情况下，二叉搜索树为完全二叉树（或者接近完全二叉树），其高度为：log2 N。最差情况下，二叉搜索树退化为单枝树，其高度为：N。所以综合而言二叉搜索树增删查改的时间复杂度为：O(N)。

这样的效率显然是无法满足我们的需求的，后面的平衡二叉搜索树 AVL 树和红黑树才能适用于内存中存储和搜索数据。

二分查找也能实现 O(log2N) 级别的查找效率，但是二分查找有两大缺陷：
1. 需要存储在支持下标随机访问的结构中，并且有序。
2. 插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除需要挪动数据。

3. 二叉搜索树的插入

插入的具体过程如下：

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

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

4. 二叉搜索树的查找

从根结点开始比较，查找 x，x 比根结点的值小则往左走，x 比根结点的值大则往右走。
最多查找高度次，走到为空，还没有找到，则这个值不存在。
不支持插入相等的值，找到 x，即可返回。

如果支持插入相等的值，意味着有多个 x 存在，一般要求查找中序的第一个 x。

5. 二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回 false。如果查找的元素存在，则分以下四种情况进行处理（假设要删除的结点为 N）：

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

相关免费在线工具

加密/解密文本

使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online

Base64 字符串编码/解码

将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online

Base64 文件转换器

将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online

Markdown转HTML

将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online

HTML转Markdown

将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online

JSON 压缩

通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

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 BSTree { typedef BSTNode<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* 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 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 { //删除 if (cur->_left == nullptr) //左为空，父亲指向我的右 { if (cur == _root) { _root = cur->_right; } else { if (cur == parent->_right) { parent->_right = cur->_right; } else { parent->_left = cur->_right; } } delete cur; } else if (cur->_right == nullptr) //右为空，父亲指向我的左 { if (cur == _root) { _root = cur->_left; } else { if (cur == parent->_right) { parent->_right = cur->_left; } else { parent->_left = cur->_left; } } delete cur; } else //左右都不为空 { //找右子树的最小结点（最左结点）替代我的位置 Node* minRightParent = cur; Node* minRight = cur->_right; while (minRight->_left) { minRightParent = minRight; minRight = minRight->_left; } cur->_key = minRight->_key; if (minRightParent->_left == minRight) { minRightParent->_left = minRight->_right; } else { minRightParent->_right = minRight->_right; } delete minRight; } return true; } } return false; } void InOrder() //外面不能访问私有，但是里面可以 { _InOrder(_root); std::cout << std::endl; } private: //中序遍历 void _InOrder(Node* root)//这里有个问题就是我在外面想传这个根结点，但是根节点是私有的，所以有两种解决方案 1.写一个 GetRoot 2.我们再套一层 { if (root == nullptr) { return; } _InOrder(root->_left); std::cout << root->_key << " "; _InOrder(root->_right); } Node* _root = nullptr; };

特性	仅 Key	Key/Value 对
数据结构目的	维护有序的唯一元素集合	建立键到值的映射关系
典型操作	插入、删除、存在性检查	插入、删除、按 key 查 value
应用举例	用户名的唯一性校验	学号关联学生详细信息
库实现	`TreeSet`（Java）	`TreeMap`（Java）

template <class K, class V> struct BSTNode //定义 key/value 对的结点 { 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 BSTree { typedef BSTNode<K, V> Node; public: bool Insert(const K& key, const V& value) { if (_root == nullptr) //如果根节点为空 { _root = new Node(key, value); 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, value); if (parent->_key < key) { parent->_right = cur; } else { parent->_left = cur; } return true; } Node* Find(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 { 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 { //删除 if (cur->_left == nullptr) //左为空，父亲指向我的右 { if (cur == _root) { _root = cur->_right; } else { if (cur == parent->_right) { parent->_right = cur->_right; } else { parent->_left = cur->_right; } } delete cur; } else if (cur->_right == nullptr) //右为空，父亲指向我的左 { if (cur == _root) { _root = cur->_left; } else { if (cur == parent->_right) { parent->_right = cur->_left; } else { parent->_left = cur->_left; } } delete cur; } else //左右都不为空 { //找右子树的最小结点（最左结点）替代我的位置 Node* minRightParent = cur; Node* minRight = cur->_right; while (minRight->_left) { minRightParent = minRight; minRight = minRight->_left; } cur->_key = minRight->_key; if (minRightParent->_left == minRight) { minRightParent->_left = minRight->_right; } else { minRightParent->_right = minRight->_right; } delete minRight; } return true; } } return false; } void InOrder() //外面不能访问私有，但是里面可以 { _InOrder(_root); std::cout << std::endl; } private: //中序遍历 void _InOrder(Node* root)//这里有个问题就是我在外面想传这个根结点，但是根节点是私有的，所以有两种解决方案 1.写一个 GetRoot 2.我们再套一层 { if (root == nullptr) { return; } _InOrder(root->_left); std::cout << root->_key << " " << root->_value << std::endl; _InOrder(root->_right); } Node* _root = nullptr; }; int main() { //1.查找单词 BSTree<string, string> dict; //BSTree<string, string> copy = dict; dict.Insert("left", "左边"); dict.Insert("right", "右边"); dict.Insert("insert", "插入"); dict.Insert("string", "字符串"); string str; while (cin >> str) { auto ret = dict.Find(str); if (ret) { cout << "->" << ret->_value << endl; } else { cout << "无此单词，请重新输入" << endl; } } //2.统计出现的次数 string arr[] = {"苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉"}; BSTree<string, int> countTree; for (auto& e : arr) { //先查找水果在不在搜索树中 //不在，则第一次出现，插入到搜索树中 //在，则只需要++查找的水果的次数 BSTNode<string, int>* ret = countTree.Find(e); if (ret == nullptr) { countTree.Insert(e, 1); } else { ret->_value++; } } countTree.InOrder(); return 0; }

C++ 二叉搜索树：从基础概念到代码实现

1. 二叉搜索树的概念

2. 二叉搜索树的性能分析

3. 二叉搜索树的插入

4. 二叉搜索树的查找

5. 二叉搜索树的删除

更多推荐文章

相关免费在线工具

6. 二叉搜索树的代码实现

7. 二叉搜索树的 key 和 key/value 对的使用场景

7.1 key 搜索场景

7.2 key/value 对的场景

7.3 核心区别总结

7.4 如何选择？

7.5 key/value 对的代码实现

C++ 二叉搜索树：从基础概念到代码实现

1. 二叉搜索树的概念

2. 二叉搜索树的性能分析

3. 二叉搜索树的插入

4. 二叉搜索树的查找

5. 二叉搜索树的删除

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具

6. 二叉搜索树的代码实现

7. 二叉搜索树的 key 和 key/value 对的使用场景

7.1 key 搜索场景

7.2 key/value 对的场景

7.3 核心区别总结

7.4 如何选择？

7.5 key/value 对的代码实现