初学二叉搜索树踩坑多？C++ 从原理到代码，搞定增删查全流程

Vect_

发布于 2025-12-18 17:55:56

2100

🎬 个人主页：Vect个人主页 🎬 GitHub：Vect的代码仓库 🔥 个人专栏: 《数据结构与算法》《C++学习之旅》《计算机基础》

⛺️Per aspera ad astra.

1. 二叉搜索树相关概念

如下图所示，二叉搜索树(binary search tree)满足下列条件：

对于根节点，左子树中所有节点的值<根节点的值<右子树中所有节点的值
任意节点的左、右字数也是二叉搜索树，同样满足条件1

而下图就不是二叉搜索树：

2. 二叉搜索树的操作

我们将二叉搜索树封装为一个类BSTree，并声明一个_root变量，指向树的根节点

// 节点类
template <class K>
    struct BSTNode {
        BSTNode<K>* _left;
        BSTNode<K>* _right;
        K _key;

        // 构造
        BSTNode(const K& val)
            :_left(nullptr)
                ,_right(nullptr)
                ,_key(val){ }
    };
// 二叉搜索树类
template <class K>
    class BSTree{
    public:
        typedef BSTNode<K> Node;
    private:
        Node* _root;
    };

2.1. 查找节点

给定目标val，可以声明一个节点cur，从二叉搜索树的根节点_root出发，循环比较cur._key和val之间的大小关系：

若val < cur._key，说明目标节点在cur的左子树，执行cur = cur._left
若val > cur._key，说明目标节点在cur的右子树，执行cur = cur._right
若val == cur._key，说明找到目标节点，跳出循环并返回该节点

与二分查找原理一致，每轮排除一半的情况，当二叉树平衡时，循环次数最多为二叉树的高度，

O(logn)

	// 查找节点 
	Node* find(const K& val) {
		Node* cur = _root;
		while (cur) {
			if (val < cur->_key) cur = cur->_left;
			else if (val > cur->_key) cur = cur->_right;
			else break;
		}
		return cur;
	}

2.2. 插入节点

给定一个待插入元素val，为了保持左子树<根节点<右子树的性质，插入流程如下：

查找插入位置： 与查找操作相同逻辑，从根节点出发，根据当前节点值和val的大小关系循环向下搜索，直到越过叶子节点（遍历到None）跳出循环
在该位置插入节点： new一个新节点，将新节点置于None的位置

注意：

二叉搜索树不允许存在重复节点，否则将违反其定义。因此，若待插入节点在树中已存在，则不执行插入，直接返回。
为了实现插入节点，我们需要借助节点pre 保存上一轮循环的节点。这样在遍历至 None时，我们可以获取到其父节点，从而完成节点插入操作。

bool insert(const K& val) {
	// 空树 直接插入
	if (_root == nullptr) {
		Node* newNode = new Node(val);
		_root = newNode;
		return true;
	}

	// 非空树 先找待插入节点的位置
	Node* cur = _root;
	Node* curPre = nullptr; // 保存cur的父节点 
	while (cur) {
		if (val == cur->_key) return false; // 重复值 不插入
		else if (val < cur->_key) {  // 小于键值 往左走 同时更新cur的父节点
			curPre = cur;
			cur = cur->_left;
		}
		else { // 大于键值 往右走 同时更新cur的父节点
			curPre = cur;
			cur = cur->_right;
		}
	}
	// cur的位置是待插入位置
	Node* newNode = new Node(val);
	// 判断cur在curPre的左边还是右边 确定新节点位置
	if (curPre->_left == cur) curPre->_left = newNode;
	else curPre->_right = newNode;

	return true;
}

2.3. 删除节点

先在二叉树中查找到目标节点，再将其删除。与插入节点一样，我们需要保证在删除操作完成后，保证二叉搜索树的“左子树 < 根节点 < 右子树”的性质不变

根据待删除节点的孩子数量，分0、1和2三种情况

待删除结点是叶子节点，直接删除

待删除节点有一个孩子，将待删除节点的子节点和其替换即可

待删除节点2个孩子，不能直接删除，需要用一个节点替换该节点，保持“左子树 < 根节点 < 右子树”的性质不变，可以选择右子树最小节点或左子树最大节点

假设我们选择右子树最小节点，如下流程：

找到待删除节点cur的右子树最小节点rightMin
用rightMin的值覆盖cur，并删除rightMin

总共有如下几种情况：

cur 有两个孩子；右子树最小节点 rightMin 就是 cur->_right；rightMin 无右孩子（A0）

触发：cur->_right 没有左孩子，且 cur->_right->_right == nullptr

操作：cur->_key = rightMin->_key；令 cur->_right = nullptr；删除 rightMin。

示意：

    cur(•)
   /     \
 (...)  rightMin

cur 有两个孩子；rightMin 就是 cur->_right；rightMin 只有右孩子（A1）

触发：cur->_right 没有左孩子，且 cur->_right->_right != nullptr

操作：cur->_key = rightMin->_key；令 cur->_right = rightMin->_right；删除 rightMin。

示意：

    cur(•)
   /     \
 (...)  rightMin
            \
             X

cur 有两个孩子；rightMin 在更下方；rightMin 无右孩子（B0）

触发：cur->_right 有左孩子，沿左链找到 rightMin，且 rightMin->_right == nullptr

操作：cur->_key = rightMin->_key；令 rightMinPre->_left = nullptr；删除 rightMin。

示意：

    cur(•)
       \
       ...
      /
 rightMin

cur 有两个孩子；rightMin 在更下方；rightMin 只有右孩子（B1）

触发：cur->_right 有左孩子，沿左链找到 rightMin，且 rightMin->_right != nullptr

操作：cur->_key = rightMin->_key；令 rightMinPre->_left = rightMin->_right；删除 rightMin。

示意：

    cur(•)
       \
       ...
      /
 rightMin
      \
       X

bool erase(const K& val) {
	// 空树无法删除
	if (_root == nullptr) return false;

	// 查找待删除节点
	Node* cur = _root;
	Node* curPre = nullptr;
	while (cur) {
		if (val < cur->_key) { // 向左找
			curPre = cur;
			cur = cur->_left;
		}
		else if (val > cur->_key) { // 向右找
			curPre = cur;
			cur = cur->_right; 
		}
		else break; // 命中
	}

	// cur为空 无法删除
	if (cur == nullptr) return false;

	//  找到cur了
	// 孩子0/1个的情况
	if (cur->_left == nullptr || cur->_right == nullptr) {
		// 找到待删除节点的孩子
		Node* curNext = cur->_left == nullptr ? cur->_right : cur->_left;

		if (cur != _root) { // 删除的不是根节点
			if (curPre->_left == cur) curPre->_left = curNext;
			else curPre->_right = curNext;
		}
		else { // 删除的是根节点
			_root = curNext;
		}
		delete cur;
	}
	else { // 2个孩子
		// 1. 找右子树最小节点
		Node* rightMin = cur->_right;
		Node* rightMinPre = cur;
		while (rightMin->_left) {
			rightMinPre = rightMin;
			rightMin = rightMin->_left;
		}

		// 2. 用rightMin的值覆盖待删除节点的值
		cur->_key = rightMin->_key;

		// 3. 删除rightMin 要处理rightMin的孩子
		Node* rightMinNext = rightMin->_right;
		if (rightMinPre->_left == rightMin) rightMinPre->_left = rightMinNext;
		else rightMinPre->_right = rightMinNext; // 右子树最小节点是cur->_right的情况
		delete rightMin;
	}
	return true;
}

再次总结：

查找阶段

用 cur 定位待删，curPre 记录父。
终止条件：命中或走到空。
注意：若支持自定义比较器，等价判断应为“!(val<key) && !(key<val)”。

0/1 个孩子：真正移除 cur 节点

curNext = (cur->_left ? cur->_left : cur->_right)。
若 cur != _root：把 curPre 的相应孩子指向 curNext。
若 cur == _root：_root = curNext。
delete cur。
要点：这是必须对“根”特判的地方（根没有父指针可改）。

2 个孩子：值覆盖 + 删后继（不移动 cur 本体）

找右子树最小：

Node* rightMin = cur->_right;
Node* rightMinPre = cur;
while (rightMin->_left) { rightMinPre = rightMin; rightMin = rightMin->_left; }

覆盖键值：cur->_key = rightMin->_key;（若有 value，一并拷/搬移）。

删除 rightMin：

Node* rightMinNext = rightMin->_right; // 只可能有右孩子或空
if (rightMinPre->_left == rightMin) rightMinPre->_left = rightMinNext;
else                                 rightMinPre->_right = rightMinNext; // 当 rightMin 就是 cur->_right
delete rightMin;

要点：这里不需要根特判，因为根节点对象没被删除，只是“值被改写”。

3. 二叉搜索树的实现

#pragma once
#include <iostream>
#include <vector>
using namespace std;

namespace BSTKey {
	template <class K>
	struct BSTNode {
		BSTNode<K>* _left;
		BSTNode<K>* _right;
		K _key;

		// 构造
		BSTNode(const K& val)
			:_left(nullptr)
			,_right(nullptr)
			,_key(val){ }
	};

	template <class K>
	class BSTree {
	public:
		typedef BSTNode<K> Node;
		BSTree() = default;

		// 析构 需要辅助析构函数
		~BSTree() { destroy(_root); _root = nullptr; }

		// 查找节点 
		Node* find(const K& val) {
			Node* cur = _root;
			while (cur) {
				if (val < cur->_key) cur = cur->_left;
				else if (val > cur->_key) cur = cur->_right;
				else break;
			}
			return cur;
		}

		bool insert(const K& val) {
			// 空树 直接插入
			if (_root == nullptr) {
				Node* newNode = new Node(val);
				_root = newNode;
				return true;
			}

			// 非空树 先找待插入节点的位置
			Node* cur = _root;
			Node* curPre = nullptr; // 保存cur的父节点 
			while (cur) {
				if (val == cur->_key) return false; // 重复值 不插入
				else if (val < cur->_key) {  // 小于键值 往左走 同时更新cur的父节点
					curPre = cur;
					cur = cur->_left;
				}
				else { // 大于键值 往右走 同时更新cur的父节点
					curPre = cur;
					cur = cur->_right;
				}
			}
			// cur的位置是待插入位置
			Node* newNode = new Node(val);
			// 判断cur在curPre的左边还是右边 确定新节点位置
			if (curPre->_left == cur) curPre->_left = newNode;
			else curPre->_right = newNode;

			return true;
		}

		bool erase(const K& val) {
			// 空树无法删除
			if (_root == nullptr) return false;

			// 查找待删除节点
			Node* cur = _root;
			Node* curPre = nullptr;
			while (cur) {
				if (val < cur->_key) { // 向左找
					curPre = cur;
					cur = cur->_left;
				}
				else if (val > cur->_key) { // 向右找
					curPre = cur;
					cur = cur->_right; 
				}
				else break; // 命中
			}

			// cur为空 无法删除
			if (cur == nullptr) return false;

			//  找到cur了
			// 孩子0/1个的情况
			if (cur->_left == nullptr || cur->_right == nullptr) {
				// 找到待删除节点的孩子
				Node* curNext = cur->_left == nullptr ? cur->_right : cur->_left;

				if (cur != _root) { // 删除的不是根节点
					if (curPre->_left == cur) curPre->_left = curNext;
					else curPre->_right = curNext;
				}
				else { // 删除的是根节点
					_root = curNext;
				}
				delete cur;
			}
			else { // 2个孩子
				// 1. 找右子树最小节点
				Node* rightMin = cur->_right;
				Node* rightMinPre = cur;
				while (rightMin->_left) {
					rightMinPre = rightMin;
					rightMin = rightMin->_left;
				}

				// 2. 用rightMin的值覆盖待删除节点的值
				cur->_key = rightMin->_key;

				// 3. 删除rightMin 要处理rightMin的孩子
				Node* rightMinNext = rightMin->_right;
				if (rightMinPre->_left == rightMin) rightMinPre->_left = rightMinNext;
				else rightMinPre->_right = rightMinNext; // 右子树最小节点是cur->_right的情况
				delete rightMin;
			}
			return true;
		}

		void inOrder() {
			_inOrder(_root);
			cout << endl;
		}

	private:
		Node* _root;

		// 后续析构
		void destroy(Node* root) {
			if (root == nullptr) return;

			destroy(root->_left);
			destroy(root->_right);
			delete root;
		}

		void _inOrder(Node* root) {
			if (root == nullptr) return;

			_inOrder(root->_left);
			cout << root->_key << " ";
			_inOrder(root->_right);
		}
	};

	void testBST() {
		BSTree<int> bst;
		vector<int> arr = { 8,3,10,1,6,14,5,7,13 };

		cout << "=== 1. 创建二叉搜索树 ===\n";
		cout << "初始数据：-> ";
		for (const auto& e : arr) cout << e << " ";
		cout << "\n创建完成数据：-> ";
		for (const auto& e : arr) bst.insert(e);
		bst.inOrder();

		cout << "=== 2. 查找数据 ===\n";
		cout << "查找不存在数据：28  查找结果：" << bst.find(28) << endl;
		cout << "查找存在数据：14  查找结果：" << bst.find(14) << endl;

		cout << "\n=== 3. 删除数据 ===\n";
		cout << "删除前的序列：->";
		bst.inOrder();
		cout << "删除节点6后的序列：->";
		bst.erase(6);
		bst.inOrder();
		cout << "删除不存在的节点86后的序列：->";
		bst.erase(86);
		bst.inOrder();

		cout << "\n销毁二叉树：->";
		bst.~BSTree();
		bst.inOrder();
	}
}

4. 二叉搜索树的应用

4.1. K模型

只有key作为关键码（需要搜索到的值），结构中只存储key即可

例如：给一个单词word，判断该单词是否正确

以词库中所有单词集合中的每个单词作为key，构建一颗二叉搜索树
在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误

又比如门禁系统，只关注对象在不在

第三节实现的就是K模型

4.2. KV模型

每个关键码key，都有与之对应的值value，即<key，value>的键值对，例如：

简单英汉词典中英文和中文是相互对应的关系，通过英文可快速找到其对应的中文，例如：<book,书>就是一种键值对
车库收费系统，一个键值记录车牌号，另一个键值记录停留时间，随后交给收费系统处理缴费事宜
统计单词出现次数，统计成功之后，给定单词就可快速找到其出现的次数，单词与其出现的次数就是<word,count>一种键值对

我们将K模型改造成KV模型

template <class K, class V>
struct BSTNode {
	K _key;
	V _value;
	BSTNode<K, V>* _left;
	BSTNode<K, V>* _right;

	BSTNode(const K& k, const V& v)
		: _key(k), _value(v), _left(nullptr), _right(nullptr) {
	}
};

template<class K, class V>
class BSTree{
public:
	typedef BSTNode<K, V> Node;
    // ... 接口实现
private:
    Node* _root = nullptr;
    // ...辅助接口实现
}
};

// 输入中文 输出对应英文
void dictionary() {
	BSTree<string, string> dict;
	dict.insert("书包", "bag");
	dict.insert("水果", "fruit");
	dict.insert("钢笔", "pen");
	dict.insert("书", "book");
	dict.insert("树", "tree");

	// 插入词库中所有单词
	string str;
	while (cin >> str) {
		auto ret = dict.find(str);
		if (ret == nullptr) cout << "输入错误或词库中未包含该词" << str << endl;
		else cout << str << "英文单词：->" << ret->_value << endl;
	}
}

// 计数
void count() {
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜"
				 , "苹果", "苹果", "西瓜"
				 ,"苹果", "香蕉", "苹果", "香蕉" };

	BSTree<string, int> cntTree;
	for (const auto& s : arr) {
		// 先查找水果在不在搜索树中
		// 1. 不在，说明水果第一次出现，则插入<水果, 1>
		// 2. 在，则查找到的节点中水果对应的次数++

		auto ret = cntTree.find(s);
		if (ret == nullptr) cntTree.insert(s, 1);
		else ret->_value++;
	}
	cntTree.inOrder();
}

完整代码请详见此链接：二叉搜索树二叉搜索树的核心价值，在于用 “左子树 < 根节点 < 右子树” 的简单规则，换来了查找、插入、删除操作的高效性 —— 平衡状态下

但需注意，二叉搜索树的性能依赖结构平衡：若插入数据有序，会退化为单链表，此时操作复杂度飙升至

O(n)

。这也催生了 AVL 树、红黑树等平衡二叉搜索树 —— 它们通过自平衡机制维持树的高度，兼顾了二叉搜索树的简洁性与稳定高效的性能，是后续深入学习的重要方向。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-10-27，如有侵权请联系 cloudcommunity@tencent.com 删除

苹果