节点中具有父指针的二叉树在删除时不断崩溃，错误为 0xDDDDDDDD

Question

我正在尝试使用 C++ 进行一些试验，并决定尝试为二叉树创建整棵树删除方法。出于某种原因，我不断收到指针错误，因为指针是 0xDDDDDDDD。

如果有人能向我解释为什么它不起作用，我将不胜感激，这样我就可以了解更多关于指针的知识。

struct Node {
    Node*  parent;
    Node *left,
         *right;
    int value;


   inline Node() : parent(nullptr), left(nullptr), right(nullptr), value(0){}

   ~Node() = default;

};

class BST {
public:
    Node* root;

    
public:
    BST() = default;
    inline BST(int i)
    {
        root = new Node();
        root->value = i;
        root->parent = nullptr;
        root->left = nullptr;
        root->right = nullptr;
    }
    BST(const BST& bst) = default;
   

    void Insert(int i);
    void DeleteAll(Node* node);


};

#include <iostream>

int main()
{
    BST t(20);
    t.root->left = new Node();
    t.root->left->value = 22;
    t.root->left->parent = t.root;

    t.root->right = new Node();
    t.root->right->value = 15;
    t.root->right->parent = t.root;



  


    t.DeleteAll(t.root);
    
}


void BST::Insert(int i)
{
   

}



void BST::DeleteAll(Node* node)
{ 
 
    Node* target = node;

    std::cout << "Probing node with value " << node->value << std::endl;


    if (node->left == nullptr && node->right == nullptr)
    {
        target = node->parent;  
        std::cout << "Node deleted with value: " << node->value << std::endl;     
        delete node;    

        if (target == nullptr)
        {
            std::cout << "Found and deleted root!" << std::endl;
            return;
        }

        std::cout << "Parents node value: " << target->value << std::endl;     
    }

    else if (node->left != nullptr)
    {
        std::cout << "Found left ptr with value: " << node->left->value << std::endl;
        target = node->left;

    }
    else if(node->right != nullptr)
    {
        std::cout << "Found right ptr with value: " << node->right->value << std::endl;
        target = node->right; 
    }

    DeleteAll(target);

}

我得到的控制台提示是：

Probing node with value 20
Found left ptr with value: 22
Probing node with value 22
Node deleted with value: 22
Parents node value: 20
Probing node with value 20
Found left ptr with value: -572662307
Probing node with value -572662307

在 DeleteAll() 函数中，当它返回到父节点以搜索是否有任何不为空的子节点时，它总是会找到我之前删除的左子节点。它不应该为空吗？

然后就崩溃了。我不知道为什么要这样做，但删除功能中可能有某些内容。这不是任何类型的家庭作业，我只是想了解为什么这不起作用。

Answer 1

当我运行你的代码时，我得到这个输出，它抛出 "read access violation":

Found left ptr with value: -572662307

-572662307 与 0xDDDDDDDD 相同，这是调试模式下的 Visual Studio 所特有的。有时你可能得不到这个值。

问题是你从来没有为 parent 分配内存（你甚至不需要，稍后会详细介绍）然后你一遍又一遍地尝试 delete 它。

您应该像这样重写代码以更好地理解它：

void DeleteAll(Node* node)
{
    printf("node: %p\n", node);
    Node* target = node;
    if (!node->left && !node->right)
    {
        target = node->parent; //this was never allocated, supposed to be NULL
        delete node; 
        if (target == nullptr) //target is now undefined, not NULL, can't be tested
            return; //we may not get here
    }
    else if (node->left != nullptr)
        target = node->left;
    else if (node->right != nullptr)
        target = node->right;

    DeleteAll(target); //could be deleting the same thing again
}

输出是这样的，有不同的数字：

node: 012C5078
node: 012D2F00
node: 012C5078
node: 012D2F00
node: DDDDDDDD

您看到重复的相同值，它正在尝试删除两次。正确的 DeleteAll 函数是这样的：

void BST::DeleteAll(Node* node)
{
    if (!node)
        return;
    DeleteAll(node->left);
    DeleteAll(node->right);
    delete node;
}

您还需要一个不同的 Delete(Node* node, int value) 函数，该函数基于 value,left,right 进行删除，一旦您正确插入项目，并且您想删除 BST 之前的一些值，就会使用该函数被摧毁。

试试这个例子：

https://gist.github.com/harish-r/a7df7ce576dda35c9660

节点中具有父指针的二叉树在删除时不断崩溃，错误为 0xDDDDDDDD

Binary Tree with parent pointer in node keeps crashing on Deletion with error 0xDDDDDDDD

c++

binary-tree

pointers

binary-search-tree