删除二进制搜索树的节点时出现问题

Question

我在C++中实现了一个二进制搜索树，但代码有一个错误，当删除一个有2个子节点的节点时，生成的树没有很好地连接，删除有0或1个子节点的方法效果很好。此代码基于以下答案：https://stackoverflow.com/a/31698320/11053027。

编辑：例如，如果a按以下顺序添加值：17、12、25，然后我尝试删除作为根的17，它就会被删除，所以当我尝试显示所有元素为：12、25、25作为根时。但如果现在我尝试删除12，它没有被删除，问题是在我第一次删除17时引起的。没有显示错误消息。

你能帮帮我吗。提前谢谢。这是代码：

Node<E> *getSuccesor(Node<E> &node) const {
auto *Succesor = node.right;
while (Succesor != nullptr) {
if (Succesor->left == nullptr) return Succesor;
Succesor = Succesor->left;
}
return Succesor;
}
void remove(Node<E> &node) {
if (&node == nullptr) return;
int nChildren = numChildren(node);
Node<E> *child;
if (nChildren == 2) {
child = getSuccesor(node);
remove(*child);
child->parent = node.parent;
child->left = node.left;
child->right = node.right;
if (&node == root)
root = child;
else {
if (&node == node.parent->right)
node.parent->right = child;
else node.parent->left = child;
}
} else {
child = (node.left != nullptr ? node.left : node.right);
if (child != nullptr)
child->parent = node.parent;
if (&node == root)
root = child;
else {
if (&node == node.parent->left)
node.parent->left = child;
else node.parent->right = child;
}
}
Size--;
}

Answer 1

很难确定，因为您还没有给我们一个最简单完整的例子，但我认为问题就在这里：

if (nChildren == 2) {
child = getSuccesor(node);
remove(*child);
child->parent = node.parent;
child->left = node.left;
child->right = node.right;

所以现在child知道了它的孩子。但他们不知道child现在是他们的父母。它们的parent指针仍然指向失效的节点(在本例中为"17"(，这会在下一次删除中扰乱逻辑。

在这些行之后，添加以下内容：

if(child->left)
child->left->parent = child;
if(child->right)
child->right->parent = child;

EDIT:if-else条件的另一个分支中也存在相同的错误，但我相信您也可以在那里看到如何修复它。