3

我计划使用排序数组来构建平衡的二叉搜索树。一切运行良好，直到程序结束。看来二叉搜索树的析构函数有问题。

错误信息：

程序收到信号 EXC_BAD_ACCESS，无法访问内存。原因：KERN_PROTECTION_FAILURE 地址：0x00007fff5f3ffff8 0x0000000100002857 在 BST_Node::~BST_Node (this=0x100100920) at BST_Node.h:18 ~BST_Node() {delete parent; 左边删除；删除权；}

#ifndef BST_NODE_H
#define BST_NODE_H

#include <cstddef>

class BST_Node {
    public:
        BST_Node(int k) : key(k), parent(NULL), left(NULL), right(NULL) {}
        ~BST_Node() {if (parent!=NULL) delete parent;if (left!=NULL) delete left;if (right!=NULL) delete right;}
        // data member
        int key;
        BST_Node* parent;
        BST_Node* left;
        BST_Node* right;
};

#endif

#include <iostream>
#include <vector>
#include "BST_Tree.h"
#include "BST_Node.h"

using namespace std;

// use recursion to construct the tree. Find the mid of the array to be the root of the subtree. Use left part of the array to construct the left subtree and right part to construct the right subtree.
BST_Node* CreateTree(vector<int> &a, int start, int end) {
    if (end<start) {
        return NULL;
    } else {
        int mid = (start+end+1)/2;
        BST_Node* p = new BST_Node(a[mid]);
        BST_Node* l_tmp = CreateTree(a, start, mid-1);
        if (l_tmp)
            l_tmp->parent = p;
        p->left = l_tmp;
        BST_Node* r_tmp = CreateTree(a, mid+1, end);
        if (r_tmp)
            r_tmp->parent = p;
        p->right = r_tmp;
        return p;
    }
}

int main() {
    vector<int> a;
    a.push_back(0);
    a.push_back(1);
    a.push_back(2);
    a.push_back(3);
    a.push_back(4);
    a.push_back(5);
    a.push_back(6);
    BST_Tree t;
    t.root = CreateTree(a, 0, 6);
    t.InOrderWalk(t.root);
    return 0;
}

非常感谢！

4

2 回答 2

2

任何所有权关系（当不再需要该对象时，一个对象负责删除另一个对象）不得有循环。在您的情况下，您的父节点拥有其子节点，反之亦然。

当根节点被删除时，它的构造函数会首先删除左孩子。孩子的析构函数将删除已经被删除的父母。

树中典型的所有权关系是父节点拥有它们的子节点。孩子有一个指向不携带所有权的父母的指针。该指针将在子节点的生命周期内保持有效，因为子节点将作为父节点销毁的一部分被删除。

所以你的析构函数应该简单地做：

BST_Node::~BST_Node() {
   delete left;
   delete right;
}

补充说明：

  • 您不需要检查空指针 - 删除空指针是安全的，并且不会执行任何操作。
  • 您应该防止复制 BST_Node 对象。隐式定义的复制构造函数和复制赋值运算符将创建另一个拥有相同子节点的对象，也会导致对象的双重删除。

表达指针所有权语义的最佳方式是使用合适的智能指针类。在您的情况下，最合适的声明是

class BST_Node {
    public:
        ~BST_Node() = default; // you can simply omit this completely

        // other things

        BST_Node* parent; // no ownership
        std::unique_ptr<BST_Node> left;  // exclusive ownership
        std::unique_ptr<BST_Node> right;
};

作为一个有用的附加效果，隐式生成的复制操作将被抑制，因为std::unique_ptr<T>不可复制。

于 2013-02-02T18:48:08.573 回答
0

只是通过代码运行，我在这一部分看到了一个问题

    if (l_tmp)
        l_tmp->parent = p;
    p->left = l_tmp;
    BST_Node* r_tmp = CreateTree(a, mid+1, end);
    if (r_tmp)
        r_tmp->parent = p;
    p->right = r_tmp;

l_tmp->parent并且r_tmp->parent都指向同一个节点p。因此，节点 p 被双重删除，一次是在调用 l_tmp 的析构函数时，另一次是在调用 r_tmp 的析构函数时。这可能是您看到错误的原因。正如 Andy 在评论中所建议的，这似乎是使用智能指针的好场景。

于 2013-02-02T18:39:08.103 回答