手搓二叉搜索树代码详解：从入门到实现（附完整注释）
一、简介和应用
二叉搜索树（Binary Search Tree，BST）是一种经典的数据结构，其特点在于每个节点的左子树所有节点值均小于该节点，右子树所有节点值均大于该节点。这种特性使得它在查找、插入、删除等操作中具备高效性（平均时间复杂度为O(log n)）。常用于需要快速检索的场景，如数据库索引、排序算法辅助等。本文将通过手写的C++代码，带您一步步实现一个基础版二叉搜索树。
二、特点和注意事项
1. 特点：
节点有序性：左子树<当前节点<右子树。
递归操作：插入、查找、删除等常用递归实现，逻辑清晰。
动态内存管理：通过new分配节点，需注意释放避免内存泄漏。
2. 注意事项：
若插入数据无序，可能导致树高度不平衡（如退化为链表），此时效率降低。实际应用中可结合平衡树（如AVL、红黑树）优化。
删除节点时需考虑多种情况（叶子节点、单分支、双分支），处理逻辑较复杂。
三、代码的实现步骤
1. 定义节点结构：包含数据值（data）、左右子节点指针（left/right）。
2. 初始化树：根节点root通过new分配，sum记录节点总数。
3. 插入操作（add）：
若树为空（sum=0），直接赋值根节点。
否则递归比较数据值：若data<当前节点值，递归左子树；反之递归右子树。若子树为空，新建节点并赋值。
4. 查找节点（get）：递归对比数据值，找到则返回节点，未找到返回nullptr。
5. 查找前驱节点（getpre）：
若当前节点为叶子节点或只有一个子树，直接返回（可能的前驱节点）。
否则递归查找左右子树中的前驱（优先左子树，若左子树无结果再查右子树）。
6. 查找最小节点（mindata）：递归向左子树遍历，直至左子树为空，返回当前节点（即最小值）。
7. 删除节点（del）：
先通过get找到目标节点（tmp）及前驱节点（pre）。
分情况处理：
目标节点为叶子节点：直接删除并更新pre的指针。
目标节点只有左子树：将左子树挂接到pre。
目标节点只有右子树：同理挂接右子树。
目标节点有左右子树：用前驱节点替换目标节点，并删除前驱节点（递归调用del）。
8. 辅助变量sum：记录节点总数，用于add函数中判断空树。
四、代码及注释
#include <iostream>
using namespace std;
// 定义节点结构
struct TreeNode {
int data = 0; // 节点数据值
TreeNode* left = nullptr; // 左子节点指针
TreeNode* right = nullptr; // 右子节点指针
};
class BinarySearchTree {
private:
TreeNode* root = new TreeNode; // 根节点
int sum = 0; // 节点总数
// 递归插入节点
void add(int data, TreeNode* root) {
if (sum == 0) { // 空树时直接赋值根节点
root->data = data;
} else {
if (data < root->data) { // 数据值小于当前节点，递归左子树
if (root->left) // 左子树非空
add(data, root->left);
else { // 左子树为空，新建节点
root->left = new TreeNode;
root->left->data = data;
}
} else { // 数据值大于当前节点，递归右子树
if (root->right)
add(data, root->right);
else {
root->right = new TreeNode;
root->right->data = data;
}
}
}
sum++; // 更新节点总数
}
// 递归查找节点
TreeNode* get(int data, TreeNode* root) {
if (!root) // 树为空或递归到底层未找到，返回空
return nullptr;
if (root->data == data) // 找到目标节点，返回
return root;
if (data < root->data) // 递归左子树
return get(data, root->left);
else // 递归右子树
return get(data, root->right);
}
// 递归查找前驱节点（当前节点或子树中的前驱）
TreeNode* getPre(int data, TreeNode* root) {
if (!root) // 树为空或递归到底层
return nullptr;
if (!root->left &&!root->right) // 当前节点为叶子节点，无前驱
return nullptr;
if (!root->left) { // 当前节点只有右子树
if (root->right->data == data) // 若右子树节点为目标节点，返回当前节点（前驱）
return root;
} else { // 当前节点有左子树
if (!root->right) { // 只有左子树且右子树为空
if (root->left->data == data)// 左子树节点为目标节点，返回当前节点
return root;
} else { // 左右子树均存在
if (root->left->data == data || root->right->data == data)
return root; // 当前节点为目标节点的前驱
}
}
// 递归查找左右子树中的前驱
if (getPre(data, root->left))
return getPre(data, root->left);
else
return getPre(data, root->right);
}
// 查找最小节点（递归左子树直至最左端）
TreeNode* minData(TreeNode* root) {
if (!root->left) // 左子树为空，当前节点为最小值
return root;
return minData(root->left); // 递归左子树
}
// 删除节点（核心逻辑）
TreeNode* del(int data, TreeNode* root) {
if (!root || (!root->left &&!root->right)) // 空树或目标节点为叶子节点
return nullptr;
TreeNode* tmp = get(data, root); // 找到目标节点
TreeNode* pre = getPre(data, root); // 找到前驱节点
bool lr = (pre->right == tmp); // 标记目标节点是否为前驱的右子节点
if (!tmp->left &&!tmp->right) { // 目标节点为叶子节点
!lr? pre->left = nullptr : pre->right = nullptr; // 根据lr更新前驱的指针
return root;
}
if (!tmp->right) { // 目标节点只有左子树
!lr? pre->left = tmp->left : pre->right = tmp->left; // 将左子树挂接到前驱
}
// 后续代码可能不完整（用户提供的代码片段在此处结束，需补充完整逻辑）
// 例如：处理目标节点有左右子树的情况，通常用前驱节点替换目标节点并删除前驱
}
};
int main() {
// 示例调用（此处省略，用户可根据需求添加测试代码）
return 0;
}五、总结
本文通过手搓代码实现了二叉搜索树的基础功能，重点在于理解递归操作的逻辑和节点间的关系处理。对于新手，建议从“插入→查找→删除”的顺序逐步调试代码，体会数据结构的动态变化。需注意，实际应用中若数据插入顺序极端（如全部递增），可能导致树退化，此时需考虑平衡树算法。掌握二叉搜索树是学习更复杂数据结构（如B树、红黑树）的基础，希望本文能帮助读者夯实算法基本功。
原创内容 转载请注明出处
