返回0后出现段错误；

Question

我编写了一个程序来测试我的二叉树，当我运行它时，该程序似乎崩溃了（btree.exe 已停止工作，Windows 正在检查解决方案...）。

当我通过调试器运行它并将断点放置在我怀疑导致它的函数 destroy_tree() 上时，它似乎按预期运行并返回到主函数。 Main 依次从程序返回，但随后光标跳回 destroy_tree() 并在其自身内递归循环。

下面是最小的代码示例，因此可以立即运行。 我的编译器是 MinGW，调试器是 gdb（我使用的是 Code::Blocks）。

#include <iostream>

using namespace std;

struct node
{
    int key_value;
    node *left;
    node *right;
};

class Btree
{
public:
    Btree();
    ~Btree();
    void insert(int key);
    void destroy_tree();

private:
    node *root;

    void destroy_tree(node *leaf);
    void insert(int key, node *leaf);
};

Btree::Btree()
{
    root = NULL;
}

Btree::~Btree()
{
    destroy_tree();
}

void Btree::destroy_tree()
{
    destroy_tree(root);

    cout<<"tree destroyed\n"<<endl;
}

void Btree::destroy_tree(node *leaf)
{
  if(leaf!=NULL)
  {
    destroy_tree(leaf->left);
    destroy_tree(leaf->right);
    delete leaf;
  }
}

void Btree::insert(int key, node *leaf)
{
    if(key < leaf->key_value)
    {
        if(leaf->left!=NULL)
            insert(key, leaf->left);
        else
        {
            leaf->left = new node;

            leaf->left->key_value = key;
            leaf->left->left = NULL;
            leaf->left->right = NULL;
        }
    }
    else if (key >= leaf->key_value)
    {
        if(leaf->right!=NULL)
            insert(key, leaf->right);
        else
        {
            leaf->right = new node;

            leaf->right->key_value = key;
            leaf->right->left = NULL;
            leaf->right->right = NULL;
        }
    }
}

void Btree::insert(int key)
{
    if(root!=NULL)
    {
        insert(key, root);
    }
    else
    {
        root = new node;

        root->key_value = key;
        root->left = NULL;
        root->right = NULL;
    }
}

int main()
{
    Btree tree;
    int i;

    tree.insert(1);

    tree.destroy_tree();

    return 0;
}

顺便说一句，我计划从 Code::Blocks 内置调试​​器切换到 DDD 来调试这些问题。 我听说 DDD 可以直观地显示指向对象的指针，而不仅仅是显示指针的地址。 您认为进行转换有助于解决这些类型的问题（数据结构和算法问题）吗？

Answer 1

destroy_tree() 被调用两次，调用一次，然后在执行从析构函数中离开 main() 后调用它。

您可能认为无论如何它都应该起作用，因为您检查 leaf!=NULL 是否，但删除不会将指针设置为 NULL。 所以当第二次调用 destroy_tree() 时你的 root 不为 NULL，

Answer 2

与您的问题没有直接关系（或者可能是），但为结构提供构造函数是一个很好的做法。 例如：

struct node
{
    int key_value;
    node *left;
    node *right;

    node( int val ) : key_val( val ), left(NULL), right(NULL) {}
};

如果你这样做，你的代码会变得更简单，因为你不需要担心在创建节点时设置指针，并且不可能忘记初始化它们。

关于 DDD，它是一个很好的调试器，但坦率地说，调试的秘诀是首先编写正确的代码，因此您不必这样做。 C++ 在这方面给了你很多帮助（比如构造函数的使用），但是你必须理解并使用它提供的设施。

Answer 3

成功摧毁树后，Btree::destroy_tree 不会将“root”设置为 0。 结果，析构函数类 destroy_tree() 再次出现，并且您试图销毁已经销毁的对象。

那将是未定义的行为:)。

Answer 4

一旦你破坏了根。
确保它是 NULL，这样它就不会尝试再次执行此操作（从析构函数）

void Btree::destroy_tree(node *leaf)
{
  if(leaf!=NULL)
  {
    destroy_tree(leaf->left);
    destroy_tree(leaf->right);
    delete leaf;

    leaf = NULL; // add this line
  }
}