2011-11-05 98 views
9

致力於在C++中實現我自己的BST,以便處理這些結構。二進制搜索樹破壞者

我在執行析構函數時遇到了麻煩。我在我的研究中發現,一個人不能真正擁有一個遞歸析構函數(由於一個標誌不允許析構函數被調用後在同一個對象上調用),但我並不確定任何以其他方式成功清理樹中的所有節點。

爲了彌補,我創建了一個輔助函數 - 但是這會在'delete n'行引發一個無法解析的外部錯誤。有小費嗎?

代碼:

void BinSearchTree::Clear(tNode* n) 
{ 
    if (n->left != NULL) 
     Clear(n->left); 
    if (n->right != NULL) 
     Clear(n->right); 
    delete n; 
    n = NULL; 
    size--; 
} 
+2

它與問題無關,但您不需要將變量'n'設置爲NULL,因爲它在函數中不再被訪問。 –

+0

@JoachimPileborg null狀態的設置只是因爲可以獨立於析構函數調用Clear來重置樹。我最初測試的是缺少一個有效的根指針,以確定樹是否已初始化,然後再讓大小數據成員跟蹤這些事情。 – DivinusVox

+0

出於好奇,有沒有人知道如果大小通常是樹的標準實現跟蹤值?我看不到它的用處,因爲在模型上迭代循環是不現實的。 – DivinusVox

回答

19

你可以有一個遞歸析構函數;你不能做的是刪除同一個對象兩次。

刪除C++中的樹可能是這樣的一個典型方式:

BinSearchTree::~BinSearchTree() 
{ 
    delete _rootNode; // will recursively delete all nodes below it as well 
} 

tNode::~tNode() 
{ 
    delete left; 
    delete right; 
} 

關於未解決的外部錯誤 - 是拋出當你試圖編譯/鏈接程序的錯誤?如果是這樣,那可能是因爲tNode類的代碼(特別是tNode析構函數,如果你聲明瞭的話)不存在或者沒有被編譯到你的項目中。

+0

這可能看起來像一個愚蠢的需求澄清,但我必須問,因爲這是不同於我見過的任何遞歸。這種遞歸方法在處理鏈表時是否比while循環更糟? – LarryK

+0

對於鏈接列表,我可能只是使用while循環,因爲它正確寫入和理解爲遞歸執行一樣容易,並且它使用固定數量的堆棧空間。另一方面,通過遞歸處理樹比使用迭代方法容易得多 - 如果您編寫一個非遞歸方法來遍歷樹,那麼通常最終會實現自己的堆棧。 –

2

只需使用一個析構函數。這聽起來像你的問題是你試圖直接調用析構函數,但是語言爲你處理。當你離開一個堆棧分配對象的作用域時,或者當你刪除一個對象時,它們被調用。

所有,如果您需要的是:

~BinSearchTree() { 
    delete left; 
    delete right; 
} 

delete將調用析構函數。

注意:它是完全安全的delete NULL,它has no effect

+0

@JeremyFriesner - 你說得對。對不起,一定比我想象的更累。 –

+0

沒有必要測試null的指針。 –

+0

是的,剛剛修好了。需要查看它以確保它是安全的,因爲我不經常使用C++。 –

3

問題是,在你的類中你可能聲明節點結構有一個自定義的析構函數,但是你不提供它,所以在鏈接時編譯器抱怨一塊失蹤。

如果在析構函數中不需要任何更多的自定義代碼,那麼您可以從結構聲明中刪除析構函數,並且程序將很好地編譯。

但是請注意,沒有任何問題可以讓子節點失效(參見Brendan Long答案)。如果您在嘗試解決您遇到的問題時還有其他問題,則遇到問題。

1

如何自動化它:

class BinSearchTree 
{ 
    std::auto_ptr<tNode> left; 
    std::auto_ptr<tNode> right; 

    BinSearchTree(BinSearchTree const&); 
    BinSearchTree& operator=(BinSearchTree const&); // private 
}; 

現在破壞是自動的。 :-)

+1

Google會說些什麼:「你的意思是'unique_ptr'」? :) – avakar

+0

僅當您打開C++ 11時纔有效。 std :: auto_ptr是完美的。 –

+1

如果您將一棵二叉搜索樹分配給另一棵,則這些孩子將被綁架。那真的是你想要的嗎? – fredoverflow

4

先前的答案指出,未解決的外部錯誤很可能是由鏈接器可以看到的翻譯單元中聲明但未定義的tNode析構函數引起的。

但是,您有第二個錯誤:您似乎認爲將n設置爲null會做一些它沒有做的事情。指針值n通過值傳遞,而不是通過引用傳遞,以便改變其值(例如,通過分配NULL)在函數返回後不起作用。

這可能會給你錯誤,當你清除樹,並期望根節點指針已被設置爲NULL,當它仍然是一個懸空指針釋放內存。結果將是運行時錯誤,而不是鏈接器錯誤。

void BinSearchTree::Clear(tNode **N) 
{ 
    tNode * n = *N; 
    if (n->left != NULL) 
     Clear(n->left); 
    if (n->right != NULL) 
     Clear(n->right); 
    delete n; 
    *N = NULL; 
    size--; 
} 

會做你期望的。

0

您還可以使用遞歸,你只需要在函數頭更改爲:

void remove(node*& root) 

,它會工作。