2

我编写了一个程序来测试我的二叉树，当我运行它时，程序似乎崩溃了（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 可以直观地显示指向对象的指针，而不仅仅是显示指针的地址。您认为进行转换是否有助于解决这些类型的问题（数据结构和算法问题）？

4

4 回答 4

4

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

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

于 2009-06-14T19:46:51.253 回答
0

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

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

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

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

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

于 2009-06-14T19:50:32.493 回答
0

Btree::destroy_tree 在成功对树进行 nuking 后不会将 'root' 设置为 0。结果，析构函数类 destroy_tree() 再次尝试销毁已经销毁的对象。

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

于 2009-06-14T19:58:03.303 回答
0

一旦你破坏了根。
确保它为 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
  }
}
于 2009-06-14T20:02:28.283 回答