C++ 二叉搜索树详解：概念、实现与场景应用

本文介绍了 C++ 中二叉搜索树（BST）的概念、性质及性能分析。详细阐述了插入、查找、删除操作的逻辑与代码实现，包括处理左右子节点为空及非空的情况。同时对比了二分查找的优劣，并展示了 BST 在 Key 搜索及 Key/Value 映射场景中的应用示例，如车牌识别、单词统计等。

GitMaster发布于 2026/3/29更新于 2026/4/132 浏览

在初阶数据结构中，我们学习了树基础的概念以及顺序结构的二叉树——堆和链式结构二叉树的实现。接下来将深入学习二叉搜索树、AVL 树、红黑树，以便更好地理解 set、map 等底层结构。本文将重点讲解二叉搜索树的概念及插入、删除等操作。

文章配图

1. 二叉搜索树的概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

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

例如以下左边图示的就是不支持插入相等值得二叉搜索树，右边就是支持插入相等值得二叉搜索树

文章配图

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

最好情况下，在此在二叉搜索树当中最为完全二叉树 (或者接近完全二叉树)，其高度为:

O(log2 N)

例如以下示例：

文章配图

最差情况下，在此二叉搜索树退化为单支树 (或者类似单支)，其高度为:

O(N)

例如以下示例：

文章配图

那么通过以上对二叉树最好和最坏情况的分析就可以得出综合而言二叉搜索树增删查改时间复杂度为：

O(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

bool Erase(const K& key) { //当根节点为空时 if (_root == nullptr) { return false; } //当前节点 Node* cur = _root; //当前节点的父节点 Node* parentcur = _root; while (cur) { //当 key 的值大于当前节点的值 if (cur->_key < key) { parentcur = cur; cur = cur->right; } //当 key 的值大于当前节点的值 else if (cur->_key > key) { parentcur = cur; cur = cur->left; } //当 key 的值等于当前节点的值 else { //当要删除的节点左孩子节点为空 if (cur->left==nullptr) { //当要删除的节点为根结点时直接改变_root 指针的指向，之后再将原根结点释放 if (cur == _root) { Node* Right = cur->right; delete cur; _root = Right; } else { //当要删除的节点 cur 是其父节点的左节点时 if (cur == parentcur->left) { parentcur->left = cur->right; delete cur; } //当要删除的节点 cur 是其父节点的右节点时 else if (cur == parentcur->right) { parentcur->right = cur->right; delete cur; } } return true; } //当要删除的节点右孩子节点为空 else if (cur->right==nullptr) { //当要删除的节点为根结点时直接改变_root 指针的指向，之后再将原根结点释放 if (cur == _root) { Node* Left = cur->left; delete cur; _root = Left; } else { //当要删除的节点 cur 是其父节点的左节点时 if (cur == parentcur->left) { parentcur->left = cur->left; delete cur; } //当要删除的节点 cur 是其父节点的右节点时 else if (cur == parentcur->right) { parentcur->right = cur->left; delete cur; } } return true; } //当要删除的节点左右孩子节点都为空 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; } } } //当找不到要删除的节点就返回 false return false; }

#include<iostream> using namespace std; template<class K> struct BSTreeNode { K _key; BSTreeNode<K>* left; BSTreeNode<K>* right; BSTreeNode(const K& key) :_key(key) , left(nullptr) , right(nullptr) { } }; template<class K> class BSTree { typedef BSTreeNode<K> Node; public: //使用编译器生成的默认构造函数 BSTree() = default; bool Insert(const K& key) { //当根节点为空时 if (_root == nullptr) { _root = new Node(key); return true; } Node* cur = _root; //节点的父节点 Node* parentcur = nullptr; while (cur) { //当 key 小于当前节点的值 if (cur->_key < key) { parentcur = cur; cur = cur->right; } ////当 key 大于当前节点的值 else if (cur->_key > key) { parentcur = cur; cur = cur->left; } //当 key 等于当前节点的值 else { return false; } } cur = new Node(key); //当新节点内的值大于父节点内的值时 if (parentcur->_key < key) { parentcur->right = cur; } //当新节点内的值小于父节点内的值时 else { parentcur->left = cur; } return true; } Node* Find(const K& key) { //当根结点为空时 if (_root == nullptr) { return nullptr; } Node* cur = _root; Node* parentcur = nullptr; while (cur) { //当 key 大于当前节点的值 if (cur->_key < key) { parentcur = cur; cur = cur->right; } //当 key 小于当前节点的值 else if (cur->_key > key) { parentcur = cur; cur = cur->left; } //当 key 等于当前节点的值 else { return cur; } } //当前二叉树中找不到值为 key 的节点 return nullptr; } bool Erase(const K& key) { //当根节点为空时 if (_root == nullptr) { return false; } //当前节点 Node* cur = _root; //当前节点的父节点 Node* parentcur = _root; while (cur) { //当 key 的值大于当前节点的值 if (cur->_key < key) { parentcur = cur; cur = cur->right; } //当 key 的值大于当前节点的值 else if (cur->_key > key) { parentcur = cur; cur = cur->left; } //当 key 的值等于当前节点的值 else { //当要删除的节点左孩子节点为空 if (cur->left == nullptr) { //当要删除的节点为根结点时直接改变_root 指针的指向，之后再将原根结点释放 if (cur == _root) { Node* Right = cur->right; delete cur; _root = Right; } else { //当要删除的节点 cur 是其父节点的左节点时 if (cur == parentcur->left) { parentcur->left = cur->right; delete cur; } //当要删除的节点 cur 是其父节点的右节点时 else if (cur == parentcur->right) { parentcur->right = cur->right; delete cur; } } return true; } //当要删除的节点右孩子节点为空 else if (cur->right == nullptr) { //当要删除的节点为根结点时直接改变_root 指针的指向，之后再将原根结点释放 if (cur == _root) { Node* Left = cur->left; delete cur; _root = Left; } else { //当要删除的节点 cur 是其父节点的左节点时 if (cur == parentcur->left) { parentcur->left = cur->left; delete cur; } //当要删除的节点 cur 是其父节点的右节点时 else if (cur == parentcur->right) { parentcur->right = cur->left; delete cur; } } return true; } //当要删除的节点左右孩子节点都为空 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; } } } //当找不到要删除的节点就返回 false 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 << " "; _Inorder(root->right); } };

#include<iostream> using namespace std; template<class K,class V> struct BSTreeNode { 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) { } }; template<class K,class V> class BSTree { typedef BSTreeNode<K,V> Node; public: //使用编译器生成的默认构造函数 BSTree() = default; bool Insert(const K& key, const V& value) { //当根节点为空时 if (_root == nullptr) { _root = new Node(key,value); return true; } Node* cur = _root; //节点的父节点 Node* parentcur = nullptr; while (cur) { //当 key 小于当前节点的值 if (cur->_key < key) { parentcur = cur; cur = cur->right; } //当 key 大于当前节点的值 else if (cur->_key > key) { parentcur = cur; cur = cur->left; } //当 key 等于当前节点的值 else { return false; } } cur = new Node(key, value); //当新节点内的值大于父节点内的值时 if (parentcur->_key < key) { parentcur->right = cur; } //当新节点内的值小于父节点内的值时 else { parentcur->left = cur; } return true; } Node* Find(const K& key) { //当根结点为空时 if (_root == nullptr) { return nullptr; } Node* cur = _root; Node* parentcur = nullptr; while (cur) { //当 key 大于当前节点的值 if (cur->_key < key) { parentcur = cur; cur = cur->right; } //当 key 小于当前节点的值 else if (cur->_key > key) { parentcur = cur; cur = cur->left; } //当 key 等于当前节点的值 else { return cur; } } //当前二叉树中找不到值为 key 的节点 return nullptr; } bool Erase(const K& key) { //当根节点为空时 if (_root == nullptr) { return false; } //当前节点 Node* cur = _root; //当前节点的父节点 Node* parentcur = _root; while (cur) { //当 key 的值大于当前节点的值 if (cur->_key < key) { parentcur = cur; cur = cur->right; } //当 key 的值大于当前节点的值 else if (cur->_key > key) { parentcur = cur; cur = cur->left; } //当 key 的值等于当前节点的值 else { //当要删除的节点左孩子节点为空 if (cur->left == nullptr) { //当要删除的节点为根结点时直接改变_root 指针的指向，之后再将原根结点释放 if (cur == _root) { Node* Right = cur->right; delete cur; _root = Right; } else { //当要删除的节点 cur 是其父节点的左节点时 if (cur == parentcur->left) { parentcur->left = cur->right; delete cur; } //当要删除的节点 cur 是其父节点的右节点时 else if (cur == parentcur->right) { parentcur->right = cur->right; delete cur; } } return true; } //当要删除的节点右孩子节点为空 else if (cur->right == nullptr) { //当要删除的节点为根结点时直接改变_root 指针的指向，之后再将原根结点释放 if (cur == _root) { Node* Left = cur->left; delete cur; _root = Left; } else { //当要删除的节点 cur 是其父节点的左节点时 if (cur == parentcur->left) { parentcur->left = cur->left; delete cur; } //当要删除的节点 cur 是其父节点的右节点时 else if (cur == parentcur->right) { parentcur->right = cur->left; delete cur; } } return true; } //当要删除的节点左右孩子节点都为空 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; } } } //当找不到要删除的节点就返回 false 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->_val << " "; _Inorder(root->right); } };

C++ 二叉搜索树详解：概念、实现与场景应用

1. 二叉搜索树的概念

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

更多推荐文章

相关免费在线工具

3. 二叉搜索树的插入

3.1 插入分析

3.2 插入代码实现

4. 二叉搜索树的查找

4.1 查找分析

4.2 查找代码实现

5. 二叉搜索树的删除

5.1 删除分析

5.2 删除代码实现

6. 二叉搜索树遍历

7. 二叉搜索树完整代码

8. 二叉搜索树 key 和 key/value 使用场景

8.1 key 搜索场景

8.2 key/value 搜索场景

C++ 二叉搜索树详解：概念、实现与场景应用

1. 二叉搜索树的概念

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

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

更多推荐文章

相关免费在线工具

3. 二叉搜索树的插入

3.1 插入分析

3.2 插入代码实现

4. 二叉搜索树的查找

4.1 查找分析

4.2 查找代码实现

5. 二叉搜索树的删除

5.1 删除分析

5.2 删除代码实现

6. 二叉搜索树遍历

7. 二叉搜索树完整代码

8. 二叉搜索树 key 和 key/value 使用场景

8.1 key 搜索场景

8.2 key/value 搜索场景