Binary Search Tree-删除节点会导致其他方法错误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;
    }
}

当然你也必须添加对节点不是叶子的情况的处理，但看起来你明白这一点。

Binary Search Tree-删除节点会导致其他方法错误c ++

Binary Search Tree- deleting a node causes other methods errors c++

c++

binary

tree

search

nodes