如何在C++中實現BST的析構函數？

-1

你將如何在C++中實現BST的析構函數？我正在做一個獨立的函數，將在析構函數中調用。這也是一個模板BST。如何在C++中實現BST的析構函數？

這是一個類，所以沒有代碼請。只是邏輯或一些僞代碼謝謝！

2016-05-21 buttonSmasher96

請參閱CComBSTR https://msdn.microsoft.com/en-us/library/zh7x9w3f.aspx –

爲什麼函數不能使用任何參數？這似乎是一個非常不尋常的限制。 – templatetypedef

我已經看到它完成的方式是使用一些遞歸函數，一直到樹葉，刪除子元素並將指針移回到根。

function recursiveRelease(root) 
if root!= null 
    if (leftchild) 
    recursiveRelease(leftchild) 
    remove leftchild from tree 
    make pointer to leftchild = nullptr 
    if (rightchild) 
    recursiveRelease(rightchild) 
    remove rightchild from tree 
    make pointer to rightchild = nullptr

之後，根被破壞;希望這有助於！

來源

2016-05-21 18:20:11

有一個O（n）時間，O（1） - 空間算法用於刪除BST中不需要任何遞歸的所有節點。這個想法如下：

如果根目錄沒有留下子項，則緩存一個指向樹的右側子項的指針，刪除根節點，然後繼續刪除曾經是右側子樹的樹。
否則，如果根目錄有左側子項，則執行tree rotation以將左側子項旋轉至根目錄。

該過程最終會刪除樹中的所有節點，不需要遞歸，只需要恆定的額外空間。

這就是說......真的很奇怪，你不能讓你的幫助函數有參數。這聽起來像是一個非常武斷的限制。你可能想問爲什麼確實如此。

來源

2016-05-21 18:22:28 templatetypedef

哦，非常整齊。感謝您寫這個答案。 – blazs

我寧願不寫任何析構函數。

只要確保BST類將unique_ptr存儲到根節點，並且每個節點都將unique_ptr-s存儲到其子節點。然後，當BST對象被破壞時，整個樹會自動被破壞。

來源

2016-05-21 18:39:36 stgatilov

如何在C++中實現BST的析構函數？

回答

相關問題