使用堆棧刪除二叉樹

我仍在使用我的二叉樹，插入，查找，最大值，最小值函數都工作得很好。所以我想接下來做一個刪除功能。我包括這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

使用堆棧刪除二叉樹

回答

相關問題