c++ - 二叉搜索树中的双重删除(？)

Question

我正在编写一个代码来测试两个二叉搜索树是否相等。

但是，每当我释放内存时，我都会遇到访问冲突错误。通过它，我看到我正在访问我的释放函数中的内存地址 0xfeefee。我在 Cell 析构函数中遇到访问冲突。

另外，我真的不知道这个功能是否有效，但我并不是真的为此寻求帮助——尽管我们仍然会感谢您的帮助。

释放函数:

~Cell(void) {
    if (left) { delete left; }
    if (right) { delete right; }
}

功能:

bool BST::isEqualTo(const BST& that) const{
    if(root <= 0 && that.root <= 0){
        return true;
    }else if(root <= 0 || that.root <= 0){
        return false;
    }
    if(root->val != that.root->val){
        false;
    }
    /*Cell* saved_node1 = new Cell(*root);
    Cell* saved_node2 = new Cell(*that.root);*/
    BST a, b, c, d;
    a.root = root->left;
    b.root = that.root->left;
    c.root = root->right;
    d.root = that.root->right;
    if(a.isEqualTo(b) && c.isEqualTo(d)){
        /*a.root = saved_node1;
        b.root = saved_node2;
        c.root = saved_node1;
        d.root = saved_node2;*/
        return true;
    }
    return false;
}

树析构函数:

void BST::destroy(void) {
    length = 0;
    delete root;
    root = nullptr;
}

Answer 1

所以，在这部分代码中

BST a, b, c, d;
a.root = root->left;
b.root = that.root->left;
c.root = root->right;
d.root = that.root->right;

您创建了 BST 对象，该对象将在函数完成后立即销毁。之后，分配给 root 指针的所有内存都将被释放。

我建议你再写一个这样的比较函数:

bool _is_equal(Cell* c1, Cell* c2)
{
    if(c1 == nullptr && c2 == nullptr)
        return true;
    else if(c1 == nullptr || c2 == nullptr)
        return false;

    return  (c1 -> val == c2 -> val) &&
            _is_equal(c1 -> left,  c2 -> left) &&
            _is_equal(c1 -> right, c2 -> right);
}

然后在你的函数中调用它

bool BST::isEqualTo(const BST& that) const
{
    return _is_equal(root, that.root);
}

当然，您应该重载 operator== 来比较两个对象。看起来会更漂亮。