二进制搜索树-删除一个节点会导致其他方法错误c++

Question

我在从BST删除节点时遇到问题。我编写了一个搜索节点的方法，效果很好，当我试图删除叶时(这是我迄今为止编写的唯一情况(，它会在打印方法中导致错误(0xDDDD…(。我想这是因为打印方法遇到了某种null，但我不知道如何解决这个问题。这是代码。。。按值删除节点方法：

void deleteNodeByValue(T val)
{
cout << "nElement to delete: " << val << " n";
Node<T>* tmp = root;
while (tmp != NULL)
{
if (val == tmp->data)
{
cout << "Element found: " << tmp->data << " n";
if (tmp->right_child == NULL && tmp->left_child == NULL)
{
delete tmp;
tmp = NULL;
size--;
}
break;
}
else if (val > tmp->data)
{
tmp = tmp->right_child;
}
else if (val < root->data)
{
tmp = tmp->left_child;
}
}      
}

和树打印：

string to_string()
{
stringstream ss;
Node<T>* tmp = root;
queue<Node<T>*> q;
while (!q.empty() || tmp != NULL)
{
if (tmp != NULL)
{
q.push(tmp);
tmp = tmp->left_child; //debugger shows error in this place
}
else
{
tmp = q.front();
q.pop();
ss << "Data: " << tmp->data;
if (tmp->left_child != NULL)
{
ss << " Left child: " << tmp->left_child->data;
}
if (tmp->right_child != NULL)
{
ss << " Right child: " << tmp->right_child->data;
}
ss << " n";
tmp = tmp->right_child;
}
}
return ss.str();

它也会导致其他方法出错，比如获取树的高度或按顺序排列树，不管怎样。我该怎么办？

Answer 1

简单地说，你删除了节点，但该节点的父节点仍然指向它。所以你试图打印一个删除的节点。

你必须记住谁是你删除的节点的父节点，并将其更新为不再指向它。

有很多方法可以做到这一点，如果我是你的话，我个人会让tmp成为双指针，但由于你的名字是newbie，这里有一个更容易阅读的解决方案：

cout << "nElement to delete: " << val << " n";
Node<T>* tmp = root;
Node<T>* parent = NULL;
while (tmp != NULL)
{
if (val == tmp->data)
{
cout << "Element found: " << tmp->data << " n";
if (tmp->right_child == NULL && tmp->left_child == NULL)
{
if (parent == NULL) root = NULL;
else {
if (parent->right_child == tmp) {
parent->right_child = NULL;
} else {
parent->left_child = NULL;
}
}
delete tmp;
size--;
}
break;
}
else if (val > tmp->data)
{
parent = tmp;
tmp = tmp->right_child;
}
else if (val < root->data)
{
parent = tmp;
tmp = tmp->left_child;
}
}    

当然，当节点也不是叶子时，您必须添加对这种情况的处理，但看起来您已经理解了这一点。