前言
二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树，其核心特性是：左子树所有节点的值小于根节点，右子树所有节点的值大于根节点。它以 O(log n) 的平均时间复杂度进行查找、插入和删除操作。
本文将以 C++ 为工具，详细讲解二叉搜索树的三个本质操作：
- 插入：节点路径的抉择
- 查找：数据的定位
- 删除：结构的重组与维护
1. 准备工作
1.1 节点定义
链式结构的树由节点构成。二叉搜索树需要定义节点结构，包含键值及左右子节点指针。
template<class K> struct BSTNode {
K _key; // 节点存放的值
BSTNode<K>* _left; // 左节点
BSTNode<K>* _right; // 右节点
BSTNode(const K& key)
:_key(key), _left(nullptr), _right(nullptr) {}
};
1.2 类框架搭建
二叉搜索树类仅需存放根节点。
template<class K> class BSTree {
typedef BSTNode<K> Node;
private:
Node* _root; // 根节点指针
};
2. 二叉搜索树的插入
bool Insert(const K& key);
2.1 逻辑讲解
插入逻辑遵循'小左大右'原则：
- 若树为空，新节点作为根节点。
- 若树非空，从根节点开始遍历：
- 若插入值小于当前节点，向左走；
- 若插入值大于当前节点，向右走；
- 直到找到空位置插入。
- 若值相等，通常视为重复数据，不插入（可根据需求调整）。
2.2 代码实现
需记录父节点以便建立连接。
if (_root == nullptr) {
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur) {
if (key < cur->_key) {
parent = cur;
cur = cur->_left;
} else if (key > cur->_key) {
parent = cur;
cur = cur->_right;
} else {
return false; // 值已存在
}
}
cur = new Node(key);
if (key > parent->_key) {
parent->_right = cur;
} else {
parent->_left = cur;
}
return true;
3. 二叉搜索树的查找
bool Find(const K& key);
3.1 逻辑讲解
查找逻辑类似插入，但不创建新节点：
- 若目标值小于当前节点，向左；
- 若目标值大于当前节点，向右；
- 若相等则返回 true，遍历结束返回 false。
3.2 完整代码
bool Find(const K& key) {
Node* cur = _root;
while (cur) {
if (key > cur->_key) {
cur = cur->_right;
} else if (key < cur->_key) {
cur = cur->_left;
} else {
return true;
}
}
return false;
}
4. 二叉搜索树的删除
bool Erase(const K& key);
4.1 逻辑分析
删除操作最复杂，需保持 BST 性质。分四种情况：
- 叶子节点：直接删除，父节点对应指针置空。
- 只有左孩子：父节点指向左孩子。
- 只有右孩子：父节点指向右孩子。
- 有两个孩子：使用替换法。通常用右子树的最小节点（或左子树的最大节点）替换待删节点的值，然后删除该最小节点（此时该最小节点必为叶子或单孩子节点）。
4.2 代码实现
bool Erase(const K& key) {
Node* parent = nullptr;
Node* cur = _root;
// 查找节点
while (cur) {
if (key > cur->_key) {
parent = cur;
cur = cur->_right;
} else if (key < cur->_key) {
parent = cur;
cur = cur->_left;
} else {
// 找到节点，执行删除
// 情况 1: 无左孩子（含叶子节点）
if (cur->_left == nullptr) {
if (cur == _root) {
_root = cur->_right;
} else {
if (cur == parent->_left) {
parent->_left = cur->_right;
} else {
parent->_right = cur->_right;
}
}
delete cur;
return true;
}
// 情况 2: 无右孩子
else if (cur->_right == nullptr) {
if (cur == _root) {
_root = cur->_left;
} else {
if (cur == parent->_left) {
parent->_left = cur->_left;
} else {
parent->_right = cur->_left;
}
}
delete cur;
return true;
}
// 情况 3: 左右孩子都有
else {
Node* minRightParent = cur;
Node* minRight = cur->_right;
// 找到右子树最小节点
(minRight->_left) {
minRightParent = minRight;
minRight = minRight->_left;
}
cur->_key = minRight->_key;
(minRightParent->_left == minRight) {
minRightParent->_left = minRight->_right;
} {
minRightParent->_right = minRight->_right;
}
minRight;
;
}
}
}
;
}
5. 关于修改键值
随意修改二叉搜索树中的键值会破坏其有序性。例如将中间节点改小可能导致其大于左子树，改大可能导致其小于右子树。因此，若需调整数据，应通过删除旧值再插入新值的方式维护结构。
6. 完整代码示例
#pragma once
#include<iostream>
#include<string>
using namespace std;
namespace wang {
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 (key < cur->_key) {
parent = cur;
cur = cur->_left;
} else if (key > cur->_key) {
parent = cur;
cur = cur->_right;
} else {
return false;
}
}
cur = new Node(key);
if (key > parent->_key) {
parent->_right = cur;
} {
parent->_left = cur;
}
;
}
{
Node* cur = _root;
(cur) {
(key > cur->_key) {
cur = cur->_right;
} (key < cur->_key) {
cur = cur->_left;
} {
;
}
}
;
}
{
Node* parent = ;
Node* cur = _root;
(cur) {
(key > cur->_key) {
parent = cur;
cur = cur->_right;
} (key < cur->_key) {
parent = cur;
cur = cur->_left;
} {
(cur->_left == ) {
(cur == _root) {
_root = cur->_right;
} {
(cur == parent->_left) {
parent->_left = cur->_right;
} {
parent->_right = cur->_right;
}
}
cur;
;
} (cur->_right == ) {
(cur == _root) {
_root = cur->_left;
} {
(cur == parent->_left) {
parent->_left = cur->_left;
} {
parent->_right = cur->_left;
}
}
cur;
;
} {
Node* minRightParent = cur;
Node* minRight = cur->_right;
(minRight->_left) {
minRightParent = minRight;
minRight = minRight->_left;
}
cur->_key = minRight->_key;
(minRightParent->_left == minRight) {
minRightParent->_left = minRight->_right;
} {
minRightParent->_right = minRight->_right;
}
minRight;
;
}
}
}
;
}
{
_InOrder(_root);
cout << endl;
}
:
_InOrder(Node* root) {
(root == ) {
;
}
_InOrder(root->_left);
cout << root->_key << ;
_InOrder(root->_right);
}
Node* _root = ;
};
}
7. 结语
本文详细介绍了二叉搜索树的核心实现逻辑。理解插入、查找与删除的底层机制，特别是删除时的节点替换策略，对于掌握数据结构至关重要。建议读者结合代码多进行练习，以巩固对指针操作及内存管理的理解。
