c++ - 删除带有堆栈的二叉树

Question

我仍在研究我的二叉树，插入、查找、最大、最小函数到目前为止都工作得很好。所以接下来我想做一个删除功能。我包含了一个可以保存的堆栈 - 啊 hell ，我只显示代码:

class Tree
{
private:
    int value_;
    Tree *root_;
    Tree *left_;
    Tree *right_;

    std::stack<Tree*> treeStack;

删除功能:

int Tree::eraseTree()
{
    while( !treeStack.empty() )
    {
        Tree *temp = treeStack.top();
        treeStack.pop();
        delete temp;
    }
    if( treeStack.empty() )
        return 1;
    else
        return -1;
}

我现在遇到错误。这不会是什么大问题 - 我尝试调试我自己的代码 - 但这次它告诉我 <deque> 中有一个错误我什至没有使用的库文件。

在程序关闭之前，我得到 System.AccessViolationException错误代码指向 deque文件。当然它不可能在那里，它必须是我的代码中的某个指针。这让我相信我没有正确地使用堆栈，或者没有正确地推送到堆栈。

我在这里做错了什么？当我在堆栈上调用 .pop 时，我实际上删除了节点吗？

编辑:

if( !root_ )
{
    root_ = new Tree(val, 0, 0);
    treeStack.push(root_);
    return val;
}

还有

Tree *parent = findInsertionPoint(val, root_);
    if( val < parent->value_ )
        parent->left_  = new Tree(val, 0, 0);
    else
        parent->right_ = new Tree(val, 0,0);

    treeStack.push(parent);
    return val;

是我将元素插入堆栈的位置。

附加问题:是否必须在构造函数中构建 std::stack ？

Answer 1

您在 deque 中崩溃，因为堆栈包含其中之一。如果您在崩溃后查看堆栈跟踪，那么您可以了解崩溃发生时您的代码正在做什么。

看起来最后的代码片段将错误的节点放入堆栈；肯定应该是新创建的节点，而不是插入点？如果向父节点添加两个节点，则父节点将在堆栈中出现两次，并被删除两次。

它可能应该更像

Tree *parent = findInsertionPoint(val, root_);
Tree *child = new Tree(val, 0, 0);
if( val < parent->value_ )
    parent->left_  = child;
else
    parent->right_ = child;

treeStack.push(child);
return val;

但我赞成 DeadMGs 建议对 left_ 和 right_ 使用智能指针(但不要将 root_ 设为 auto_ptr，如果它由所有节点共享)，并让它们为您清理。我不确定我是否明白堆栈的意义；如果是为了加速树的破坏，那么在添加复杂且容易出错的优化之前问自己两个问题:

• 它是否足够慢，值得花费开发/调试成本进行优化？
• 在树旁边构建和维护堆栈是否值得花费额外的运行时间和内存成本？

还有你的附加问题:stack 将在构造函数中构建，但你不必编写任何代码来完成它。它的默认构造函数将被自动调用，这将为您提供一个可用的空堆栈。

此外，除非这是一个学习练习，否则您应该使用 std::multiset 而不是重新发明它。