如何從內存中刪除二叉搜索樹？

Question

我有一個BST，它是C++中的一個鏈表。我如何從內存中刪除整個事物？它會從類功能完成嗎？

Answer 1

執行樹的後序遍歷（即訪問父母之前的子節點），並在您訪問它時刪除每個節點。

這是否與類有關取決於你的實現。

Answer 2

由於提供的信息有限....

如果您分配了新的或的malloc（或相關的功能），比你需要遍歷了所有節點和免費或刪除節點。

另一種方法是把shared_ptr's (and weak_ptr's to kill cyclics)在分配 - 只要你做正確，你將不必釋放節點手動

如果您使用的是你在互聯網上拿起比所提供的質量實現班級不泄漏，你不必擔心任何事情。

Answer 3

只要刪除兒女

struct TreeNode { 
    TreeNode *l, *r, *parent; 
    Data d; 

    TreeNode(TreeNode *p) { l = nullptr; r = nullptr; parent = p; } 
    TreeNode(TreeNode const &) = delete; 
    ~TreeNode() { 
     delete l; // delete does nothing if ptr is 0 
     delete r; // or recurses if there's an object 
    } 
}; 

，或者如果你正在使用unique_ptr或一些這樣的，這還沒有必要：

struct TreeNode { 
    unique_ptr<TreeNode> l, r; 
    TreeNode *parent; 
    Data d; 

    TreeNode(TreeNode *p) { l = nullptr; r = nullptr; parent = p; } 
    TreeNode(TreeNode const &) = delete; 
    ~TreeNode() = default; 
}; 

Answer 4

使用智能指針，並忘掉它。

Answer 5

如果你有機會到鏈表本身，這是小菜一碟：

// Making liberal assumptions about the kind of naming/coding conventions that might have been used... 
ListNode *currentNode = rootNode; 

while(currentNode != NULL) 
{ 
    ListNode *nextNode = currentNode->Next; 
    delete currentNode; 
    currentNode = nextNode; 
} 

rootNode = NULL; 

如果這是BST的定製FPGA實現，那麼這很可能是它的內部工作原理，如果它有綁定到一個特定的數據結構。

如果你沒有訪問內部，那麼Potatoswatter的答案應該是現貨。假設BST按照他們的建議進行設置，那麼簡單地刪除根節點應該會自動刪除所有分配的內存，因爲樹下的每個父節點都將刪除其子節點。

如果你問如何去跨越一個二叉樹遍歷手動，那麼你會做以下遞歸步驟：

void DeleteChildren(BSTNode *node) 
{ 
    // Recurse left down the tree... 
    if(node->HasLeftChild()) DeleteChildren(node->GetLeftChild()); 
    // Recurse right down the tree... 
    if(node->HasRightChild()) DeleteChildren(node->GetRightChild()); 

    // Clean up the data at this node. 
    node->ClearData(); // assume deletes internal data 

    // Free memory used by the node itself. 
    delete node; 
} 

// Call this from external code. 
DeleteChildren(rootNode); 

我希望我沒有理解錯了這裏的東西的這幫助。