views:

499

answers:

5

I have a BST which is a linked list in C++. How would I delete the whole thing from memory? Would it be done from a class function?

+1  A: 

Perform a post-order traversal of the tree (i.e. visiting children before parents), and delete each node as you visit it.

Whether or not this has anything to do with classes depends entirely on your implementation.

Tyler McHenry
A: 

With the limited information provided ....

If you allocated the nodes with new or malloc (or related functions) than you need to traverse over all the nodes and free or delete them.

An alternative is to put shared_ptr's (and weak_ptr's to kill cyclics) in your allocations -- provided you do it correctly you won't have to free the nodes manually

If you used a quality implementation that you picked up on the internet than provided the classes don't leak, you don't have to worry about anything.

Hassan Syed
+3  A: 

Just delete the children:

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

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

or if you're using auto_ptr or some such, that's not even needed:

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

    TreeNode( TreeNode *p ) { parent = p; }
    TreeNode( TreeNode const & ){ throw logic_error( "can't copy TreeNode" ); }
    //~TreeNode() {}
};
Potatoswatter
If you need to retain a portion of the subtree, you can just provide a Detach() method that will de-list a node from its parent. Then the delete won't cascade down to the subtree you want to keep.
Scott Smith
With `auto_ptr`, that would be accomplished just by assigning eg `auto_ptr<TreeNode> outside_ptr = my_node.l`.
Potatoswatter
I would like to raise a warning: this sample is evil and is likely to cause crashes. The problem is that the copy / assignment operator of the `auto_ptr` have weird semantics... `const TreeNode TreeNode copy(node); node.l->data;` will crash (hopefully immediately).
Matthieu M.
@Matthieu: unless the `auto_ptr` object is the `...` in your code, no `auto_ptr` semantics are in that at all. `auto_ptr` assignment is used for `detach`, as Scott and I just mentioned. You don't want to access an invalidated pointer post-`detach`. (`auto_ptr` invariably implements `move` semantics and is being obsoleted by C++0x's more pervasive support in that regard, duly noted.)
Potatoswatter
I was reusing your implementation of `TreeNode` based on `auto_ptr`, thus the copy constructor created automatically for `TreeNode` by the compiler will be based on the copy constructor from `auto_ptr` with its bastard semantic in the formation of `copy`, and `node` will end up being modified despite being `const` which is definitely weird. I am all for using smart pointers here, but unfortunately you still have to write down the Copy Constructor and Assignment Operator by yourself if you want a proper semantic.
Matthieu M.
@Matthieu: Ah, I see. "Cool." Gotta be genuinely careful, though, when using a tree structure for a DAG like that. I'll fix the answer… hmm, maybe there's a way to do that with templates but it's too late :v(
Potatoswatter
A: 

Use smart pointers and forget about it.

wilhelmtell
+1  A: 

If you have access to the linked list itself, it's a piece of cake:

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

If this is a custom implemention of a BST, then this may well be how it works internally, if it has tied itself to a particular data structure.

If you don't have access to the internals, then Potatoswatter's answer should be spot on. Assuming the BST is setup as they suggest, then simply deleting the root node should automatically delete all the allocated memory as each parent down the tree will delete its children.

If you are asking how to go about iterating across a binary tree manually, then you would do the following recursive step:

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

I hope I've not missed the point here and that something of this helps.

xan
Why would a function ClearData() be needed? Why not delete the node? Does this also delete the root node?
Phenom
I included ClearData() to indicate that at each node *something* needs to be done to free the memory taken by the data that the node holds (if any). If the node just has a pointer to external data (quite likely) then ClearData() might simply NULL the pointer. If the tree actually allocated memory for the data itself (say each node directly held string data as a char[] that it had allocated) then ClearData() would need to delete[] this array. What I was trying to imply was that the steps are: 1) Clear any data held by each node (this could be done in the destructor) 2) Delete the node itself.
xan