如何从内存中删除二叉搜索树？

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); 

我希望我没有理解错了这里的东西的这帮助。