c++ - 破坏二叉搜索树时发生读取访问冲突

Question

晚上好。 当我尝试销毁 BST 时，出现访问冲突异常错误。 之前有过关于此的帖子，我复制了他们接受的答案的回复，但仍然没有得到预期的结果。 所以我有这个二叉搜索树实现。一切正常，直到我的代码从 int main() 函数到达“return 0”。

我会给你留下一些代码。

PQBST::~PQBST()
{
    destroy();
}

inline void PQBST::destroy()
{
    if (root)
        destroy(root);
}

void PQBST::destroy(Node* node)
{
    if (node->left) // this is where it gives me and access violation exception 0xDDDDDDDD
        destroy(node->left);
    if (node->right)
        destroy(node->right);
    delete node;
}

我知道当你尝试删除已经被释放的东西时会抛出这种错误，但我不明白为什么当我在我的程序中调用一次 destroy 函数时它会尝试销毁我的 BST 两次。应用程序(当我完成它时)。 我评论了我手动销毁 BST 的部分，在达到“return 0”后，它再次给了我

Unhandled exception thrown: read access violation.
node was 0xFF12C6AB

所以它不是 0xDDDDDDDD 但仍然是一个错误。 :|

我的节点如下所示:

struct Node
{
    Human info;
    Node * left;
    Node * right;
    Node() {};
    Node(Human value)
        : info(value), left(NULL), right(NULL)
    {

    }
};

我的 BST 类只有 Node* root 。 我希望我给了你足够的信息。 谢谢。

编辑:我的节点现在看起来像这样:

    struct Node
{
    Human info;
    Node * left;
    Node * right;
    Node() { left = NULL, right = NULL;  }
    Node(Human value): info(value), left(NULL), right(NULL){}
    Node(Human value, Node* left, Node* right) : info(value), left(left), right(right) {}
    Node& operator=(const Node& n)
    {
        info = n.info;
        left = n.left;
        right = n.right;

        return *this;
    }

    Human getInfo() const { return info; }
    Node* getLeft() { return left; }
    Node* getRight() { return right;  }
    ~Node() { };
};

我的 PQBST:

class PQBST
{
private:
    Node * root;
    int m; //spaceship size - given by the user

public:
    PQBST() { root = NULL; }
    PQBST(int m) : root(NULL), m(m) {}
    PQBST(Node* root, int m);
    ~PQBST();

PQBST::PQBST(Node * root, int m)
{
    this->root = root;
    this->m = m;
}

Answer 1

如果您要删除 BST，我建议您执行 post order traversal 。这将递归地访问左、右，然后删除该节点。只要树构建正确，这就会起作用。

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

话虽如此，我建议不要尝试手动管理内存并使用 std::unique_ptr<T>哪里T是你的节点类型。我会在你的 BST 中将它们定义为 std::unique_ptr<Node> left, right; 。这完全避免了这个问题。