使用堆栈删除二叉树

我仍在使用我的二叉树，插入，查找，最大值，最小值函数都工作得很好。所以我想接下来做一个删除功能。我包括这saves-啊地狱，我就只显示代码堆栈：使用堆栈删除二叉树

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;

就是我推堆在我的元素。

附加问题：是否必须在ctor中构建std :: stack？

来源

2010-06-26 IAE

我看到'eraseTree'是'Tree'类的一部分，也许你有'this'在'treeStack'所以你在做'删除this' – cristis 2010-06-26 09:15:12

我已经从来不太熟悉这个指针，或者它实际上是什么。我需要做些什么来确保这个指针不再抱怨？ – IAE 2010-06-26 09:16:53

在第一眼看，我看不到任何失败。这可能是它不适用于std :: stack的原因，但是如果错误不在发布的代码中，也许你应该在代码中包含构建堆栈的代码。 @cristis是否足以检查（temp！= this）还是不接受这项工作？ – InsertNickHere 2010-06-26 09:19:11

您在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而不是重新创建它。

来源

2010-06-26 10:33:01

+1表示std :: stack是默认使用std :: deque的适配器。尽管如此，我不会称之为无用的练习。实施树是一个很好的学术实践！也许他会希望在某一天实施kd-tree，trie或其他某种树结构，因为他们正在使用的平台没有方便的库。它也会帮助他了解std :: set/std :: map实际上是多么优秀。 – stinky472 2010-06-27 12:51:10

@ stinky472：我没有把它称为“无用的练习”。正如你所说，实施一棵树当然是一个重要的事情要了解。 – 2010-06-27 13:05:06

这听起来像你可能会删除两次。

确保您正在删除的内容不会在其他地方使用或删除，特别是在调用您的eraseTree（）方法后。

来源

2010-06-26 09:20:30 Raceimaztion

我已经包含了插入元素，不，这是我的第一个删除函数。擦除功能是迄今为止在我的程序中调用的最后一件事。 – IAE 2010-06-26 09:25:46

你有没有试过把删除掉？我发现，很烦人的是，很多时候C++会自动删除我分配的所有东西，并且如果我自己删除它，我会抱怨。 – Raceimaztion 2010-06-26 09:37:17

将root_*,left_*和right_*更改为auto_ptrs以确保其销毁。那么当你来删除一个节点时，你可以直接删除root_.release（）;一切都很好。要问你为什么使用堆栈。

来源

2010-06-26 09:46:51 Puppy

我不明白你的意思。如果我想删除整个树而不必沿着树再次返回，我只需将所有指针存储在堆栈中。提取的第一个指针位于树的底部。然后我只是删除内容。这就是为什么我想要一个堆栈。 auto_ptrs将如何帮助我做到这一点？ – IAE 2010-06-26 09:56:16

@SoulBeaver：如果您使用auto_ptrs，则不必在树上向上或向下循环。你可以删除根节点，整个树就会关闭。有了auto_ptr，销毁就会自动化并得到保证。你不需要打扰任何堆栈垃圾。 – Puppy 2010-06-26 10:28:46

我不认为auto_ptr是一个不错的选择......我建议使用shared_ptr代替。 – EmbeddedProg 2010-06-26 11:07:13

您在deque中出错，因为默认情况下，std :: stack将此类用作内部容器。看看栈定义：

template<class _Ty, class _Container = deque<_Ty> > class stack;

来源

2010-06-26 10:37:54

使用堆栈删除二叉树

回答

相关问题