c++中如何实现二叉搜索树的删除节点操作_c++树结构维护算法【详解】

BST删除节点需分三类处理：叶子节点直接删除并置空父指针；仅一子节点则用子节点顶替并修正父节点对应指针；两子节点须用中序后继替换值后递归删除后继，且后继可能带右子树需正确挂载。

删除节点时如何处理三种子节点情况

二叉搜索树（BST）删除节点的核心难点在于：被删节点的子节点数量不同，修复方式完全不同。不能只靠“找到就删”，必须按 node->left == nullptr && node->right == nullptr、node->left == nullptr || node->right == nullptr、node->left != nullptr && node->right != nullptr 三类分别处理。

常见错误是统一用中序后继替换却忘了更新后继的父指针，或在单子节点情况下直接用子节点覆盖却未修正其父节点的对应指针（比如该节点是父节点的左子还是右子没判断清楚）。

• 叶子节点：直接 delete 并置空父节点对应指针
• 仅一个子节点：用该子节点“顶替”被删节点位置，注意修改父节点的 left 或 right 指针
• 两个子节点：必须用中序后继（右子树最左节点）或中序前驱（左子树最右节点）替换值，再递归删除那个后继/前驱节点——它必然是叶子或仅一子，否则逻辑不闭环

中序后继查找与链接断开的关键细节

选中序后继（而非前驱）是惯例，但实现时容易忽略：后继节点可能有右子树。此时不能直接把后继的右子树丢弃，而要将其挂到后继原父节点的左指针上（因为后继是“最左”，所以它一定是其父节点的左子）。

更隐蔽的问题是：若后继节点就是待删节点的右子（即右子树无左分支），那么后继的父节点就是待删节点本身，此时直接用 node->right 替换即可，无需额外断链。

立即学习“C++免费学习笔记（深入）”；

TreeNode* findSuccessor(TreeNode* root) {     root = root->right;     while (root->left != nullptr) {         root = root->left;     }     return root; } 
Treenode deleteNode(TreeNode root, int key) { if (!root) 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 && !root->right) { delete root; return nullptr; } else if (!root->left) { TreeNode tmp = root->right; delete root; return tmp; } else if (!root->right) { TreeNode tmp = root->left; delete root; return tmp; } else { TreeNode* succ = findSuccessor(root); root->val = succ->val; // 关键：递归删除 succ，不是 root->right = succ->right root->right = deleteNode(root->right, succ->val); } } return root; }

递归实现中为什么必须返回 TreeNode*

因为 c++ 中函数参数默认传值，TreeNode* root 是指针的副本，修改形参本身（如 root = nullptr）不影响调用方的指针。只有通过返回新根并由上层赋值，才能真正切断旧连接。

典型反例：有人写 if (isLeaf) { delete root; root = nullptr; }，这只会让函数内局部变量 root 变成空，上层调用处的指针仍指向已释放内存，后续访问必然崩溃。

• 每次递归调用都必须接收返回值：root->left = deleteNode(root->left, key)
• 叶子节点删除后必须返回 nullptr，否则父节点的 left/right 仍指向已释放地址
• 单子节点场景下，返回子节点指针，相当于“把子节点提到当前位”，同时自动解绑原父子关系

非递归删除的指针维护陷阱

手动维护父指针的迭代写法看似直观，但极易出错：需同时追踪 current 和 parent，且必须在每步移动前记录谁是父节点。尤其当删除的是根节点时，parent 为 nullptr，所有指针修正逻辑都要分支处理。

更大的坑在于：找到后继后，要从后继的父节点“摘下”它。如果后继就是 current->right，那它的父节点是 current；否则父节点在右子树中，得重新查找——这会让代码膨胀且难验证。

除非有明确性能约束（如栈空间极度受限），否则递归更安全。迭代版本唯一优势是可避免最坏 O(h) 栈深度，但实际 BST 若不平衡，h 可能接近 n，此时先做平衡化（如转 AVL）比硬写迭代删除更治本。