C++ 二叉搜索树（BST）原理与实现

本文介绍二叉搜索树（BST）的概念、性能分析及核心操作（插入、查找、删除）。详细阐述了 BST 的定义、中序遍历有序性、时间复杂度（最好 O(logN)，最坏 O(N)），并提供了基于 C++ 模板的 Key 及 Key/Value 版本代码实现，涵盖停车场管理、拼写检查、字典及词频统计等应用场景。

山野来信发布于 2026/3/270 浏览

C++ 二叉搜索树（BST）原理与实现

一、概念

二叉搜索树也称二叉排序树。它要么是空树，要么满足下面这套'大小规则'（这就是 BST 的灵魂）：

若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值。
若它的右子树不为空，则右子树上所有结点的值均大于它的根结点的值。
它的左右子树也分别为二叉搜索树（也要继续满足上面 1、2）。

换句话说：对任意结点，都要满足左边都比我小，右边都比我大，而且子树也要同样遵守。

二叉搜索树支持中序遍历（左 - 根 - 右）。如果一棵二叉树是 BST，那么对它做中序遍历得到的结果一定是一个有序序列。

二、二叉搜索树的性能分析

BST 的插入、查找、删除，真正花多少时间，主要取决于一个东西：树高（高度越小，走的路越短）。

最好情况：BST 是一棵完全二叉树此时树高约为：log2(N) 所以增删查改都大约是：O(log2 N)
最坏情况：BST 退化成单支树（一边倒，像链表）此时树高约为：N 所以增删查改会变成：O(N)

综合而言，二叉搜索树的增删查改时间复杂度为：O(N)（按最坏情况算）。

为什么后面还要学二叉平衡树？因为有些场景不能接受'最坏 O(N)'，就需要 AVL 树、红黑树这类二叉平衡树来把高度控制在 O(logN)，从而稳定地快。

另外，二分查找也可以做到 O(log2 N)，但它有两个问题：

必须支持随机访问（典型是数组）。
数据必须有序。而有序数组要插入/删除一个元素，通常需要大量移动元素，效率不高。

所以：想要'查找快'，又想要'插入/删除也相对方便'，平衡 BST 就很有价值。

情况	树形态	树高	查找/插入/删除
最好	完全二叉树	log2(N)	O(log2 N)
最坏	单支树（退化）	N	O(N)

三、二叉搜索树的插入

BST 的插入，本质就是：按大小规则一路往下走，直到走到空位置，把新结点挂上去。

插入过程：

先看根结点是否为空。
- 若为空，直接用待插入值构造根结点。
若不为空：
- 把当前结点 cur 指向根，从根开始找插入位置；
- 比较插入值和 cur 的值：
  - 小：往左子树走
  - 大：往右子树走
- 当 cur 走到空（nullptr）时，说明位置找到了：把新结点插入，并挂到它父结点的左/右上。
二叉搜索树不允许冗余（相等）元素。当需要冗余元素时，这里用不着二叉搜索树，用后面的二叉平衡树。当然，如果需要实现插入相同值的元素，也是可以实现的，只需要提前规定：
- 比如遇到相同值时都插入到右子树，或者都插入到左子树。
- 归结为：遇到相同元素时，一定要优先去某一个方向。

步骤	当前状态	判断	下一步
1	cur 指向根	root 是否为空	为空：root=new；不空：进入循环
2	循环	key 与 cur->_key 比较	小：cur=cur->_left；大：cur=cur->_right

相关免费在线工具

加密/解密文本

使用加密算法（如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 { BSTNode(const K& key) : _key(key), _left(nullptr), _right(nullptr) {} K _key; BSTNode<K>* _left; BSTNode<K>* _right; }; // Binary Search Tree 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* 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 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 { // 0-1 个孩子的情况 // 删除情况 1 2 3 均可以直接删除，改变父亲对应孩子指针指向即可 if (cur->_left == nullptr) { if (parent == nullptr) { _root = cur->_right; } else { if (parent->_left == cur) parent->_left = cur->_right; else parent->_right = cur->_right; } delete cur; return true; } else if (cur->_right == nullptr) { if (parent == nullptr) { _root = cur->_left; } else { if (parent->_left == cur) parent->_left = cur->_left; else parent->_right = cur->_left; } delete cur; return true; } else { // 2 个孩子的情况 // 删除情况 4，替换法删除 // 假设这里我们取右子树的最小结点作为替代结点去删除 // 这里尤其要注意右子树的根就是最小情况的情况的处理，对应课件图中删除 8 的情况 // 一定要把 cur 给 rightMinP，否则会报错。 Node* rightMinP = cur; Node* rightMin = cur->_right; while (rightMin->_left) { rightMinP = rightMin; rightMin = rightMin->_left; } cur->_key = rightMin->_key; if (rightMinP->_left == rightMin) rightMinP->_left = rightMin->_right; else rightMinP->_right = rightMin->_right; delete rightMin; return true; } } } return false; } void InOrder() { _InOrder(_root); cout << endl; } private: void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); } private: Node* _root = nullptr; };

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 BSTree { typedef BSTNode<K, V> Node; public: BSTree() = default; BSTree(const BSTree<K, V>& t) { _root = Copy(t._root); } BSTree<K, V>& operator=(BSTree<K, V> t) { swap(_root, t._root); return *this; } ~BSTree() { Destroy(_root); _root = nullptr; } 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* cur = _root; while (cur) { if (cur->_key < key) { cur = cur->_right; } else if (cur->_key > key) { 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 (parent == nullptr) { _root = cur->_right; } else { if (parent->_left == cur) parent->_left = cur->_right; else parent->_right = cur->_right; } delete cur; return true; } else if (cur->_right == nullptr) { if (parent == nullptr) { _root = cur->_left; } else { if (parent->_left == cur) parent->_left = cur->_left; else parent->_right = cur->_left; } delete cur; return true; } else { Node* rightMinP = cur; Node* rightMin = cur->_right; while (rightMin->_left) { rightMinP = rightMin; rightMin = rightMin->_left; } cur->_key = rightMin->_key; if (rightMinP->_left == rightMin) rightMinP->_left = rightMin->_right; else rightMinP->_right = rightMin->_right; delete rightMin; return true; } } } return false; } void InOrder() { _InOrder(_root); cout << endl; } private: void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_key << ":" << root->_value << endl; _InOrder(root->_right); } void Destroy(Node* root) { if (root == nullptr) return; Destroy(root->_left); Destroy(root->_right); delete root; } Node* Copy(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; } private: Node* _root = nullptr; }; int main() { BSTree<string, string> 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; } } return 0; } int main() { string arr[] = {"苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉"}; BSTree<string, int> countTree; for (const auto& str : arr) { // 先查找水果在不在搜索树中 // 1、不在，说明水果第一次出现，则插入<水果，1> // 2、在，则查找到的结点中水果对应的次数++ // BSTreeNode<string, int>* ret = countTree.Find(str); auto ret = countTree.Find(str); if (ret == NULL) { countTree.Insert(str, 1); } else { ret->_value++; } } countTree.InOrder(); return 0; }

C++ 二叉搜索树（BST）原理与实现

C++ 二叉搜索树（BST）原理与实现

一、概念

二、二叉搜索树的性能分析

三、二叉搜索树的插入

更多推荐文章

相关免费在线工具

四、二叉搜索树的查找

五、二叉搜索树的删除

六、二叉搜索树代码实现

七、二叉搜索树 key 和 key/value 使用场景

7.1 key 搜索场景

7.2 key/value 搜索场景

7.3 key/value 二叉搜索树代码实现

C++ 二叉搜索树（BST）原理与实现

C++ 二叉搜索树（BST）原理与实现

一、概念

二、二叉搜索树的性能分析

三、二叉搜索树的插入

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

更多推荐文章

相关免费在线工具

四、二叉搜索树的查找

五、二叉搜索树的删除

六、二叉搜索树代码实现

七、二叉搜索树 key 和 key/value 使用场景

7.1 key 搜索场景

7.2 key/value 搜索场景

7.3 key/value 二叉搜索树代码实现