在C++中实现二叉搜索树的删除节点操作，核心在于根据待删除节点的子节点数量分情况处理，并保持二叉搜索树的有序性质。删除操作通常借助递归完成，通过返回更新后的子树根节点来维护整棵树的结构。
二叉搜索树节点定义
首先给出基础的节点结构，使用结构体存储键值与左右子节点指针。
#include <iostream>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
删除节点的三种情况
删除节点时，按照子节点情况分为以下三类：
- 叶子节点：直接删除，父节点对应指针置空。
- 只有一个子节点：用子节点替换当前节点。
- 有两个子节点：找到右子树的最小节点（或左子树最大节点）替换当前节点，再删除那个最小节点。
递归删除函数实现
下面给出完整的删除函数代码，使用递归方式在二叉搜索树中查找并删除指定值。
// 查找右子树最小节点并删除它，返回最小节点的值
int findMinAndDelete(TreeNode*& node) {
if (node->left != nullptr) {
return findMinAndDelete(node->left);
}
int minVal = node->val;
TreeNode* temp = node;
node = node->right; // 最小节点可能有右子节点
delete temp;
return minVal;
}
// 删除值为key的节点，返回更新后的子树根
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) {
return nullptr;
}
if (key < root->val) {
root->left = deleteNode(root->left, key);
} else if (key > root->val) {
root->right = deleteNode(root->right, key);
} else {
// 找到要删除的节点
if (root->left == nullptr) {
TreeNode* rightChild = root->right;
delete root;
return rightChild;
} else if (root->right == nullptr) {
TreeNode* leftChild = root->left;
delete root;
return leftChild;
} else {
// 有两个子节点
root->val = findMinAndDelete(root->right);
}
}
return root;
}
中序遍历验证
删除完成后，可通过中序遍历检查树是否仍保持升序。
void inorder(TreeNode* root) {
if (root == nullptr) return;
inorder(root->left);
std::cout << root->val << " ";
inorder(root->right);
}
内存与异常注意
在C++中手动管理内存时，删除节点务必使用delete释放原节点，避免内存泄漏。若树中可能不存在目标值，递归到空节点直接返回即可，不需要额外抛异常。对于频繁删除插入的场景，可考虑使用智能指针简化资源管理。
二叉搜索树的删除操作时间复杂度与树高相关，平衡树下为O(log n)，最坏退化为链表时为O(n)。
小结
掌握C++二叉搜索树删除节点的关键在于理清三种子树情形，并利用递归安全地替换与释放节点。熟练该算法有助于理解更复杂的平衡树与符号表实现。