CODEWITHSUNDEEP
ctreefree
user2213470
user2213470

Reputation: 89

How to free tree effectively

How can I free this tree effectively? That algorithm should work for any given node in such tree. So I'll have pointer to node, and that node will be "root" node. And I want to free everything below that node. enter image description here

Every node in tree is this struct:

  typedef struct tag
  {
      struct tag* parent;
      struct tag* nextSibling;
      struct tag* previousSibling;
      struct tag* firstChild;
      struct tag* lastChild;     
      char* name;
      char* text;     
  }node;

Upvotes: 0

Views: 265

Answers (3)

Dariusz
Dariusz

Reputation: 22271

Use any of the standard tree-traversal mechanisms and delete all elements.

http://en.wikipedia.org/wiki/Tree_traversal

Upvotes: 1

Bill Lynch
Bill Lynch

Reputation: 81976

I imagine this would work. But in reality, Dariusz is correct. You just use a valid tree traversal, and perform your operation on each node.

The question changed: And since you want this to operate on any node in the tree, just find the root first. It's much easier to write a tree traversal that progresses in one direction, than up and down the tree.

You've changed the question from deleting a tree, to deleting a subset of a tree. So, instead, let's do this. Remove the element from the tree first (remove_node). and then perform the same free that we would have done before.

void remove_node(node *self) {
    if (self->previousSibling)
        self->previousSibling->nextSibling = self->nextSibling;
    if (self->nextSibling)
        self->nextSibling->previousSibling = self->previousSibling;
    if (self->parent && self->parent->firstChild == self)
        self->parent->firstChild = self->nextSibling;
    if (self->parent && self->parent->lastChild == self)
        self->parent->lastChild = self->previousSibling;
}

void free_node(node *self) {
    // Free one node. Perhaps this is:
    free(self->name);
    free(self->text);
    free(self);
}

void iterate_nodes(node *root, void op(node *self) ) {
    if (root == NULL)
        return;
    iterate_nodes(root->nextSibling, op);
    iterate_nodes(root->firstChild, op);
    op(root);
}

int main() {
    node *node = NULL; // Some node in the tree...
    remove_node(node);
    iterate_nodes(node, free_node);
}

Upvotes: 1

Adam Rosenfield
Adam Rosenfield

Reputation: 400454

You can use a standard post-order tree traversal algorithms to free the whole tree. To make it work from any given node, just start by traversing all of the parent links to the root. For example:

void free_tree(node *n)
{
    // Find the root node of the tree
    while(n->parent)
        n = n->parent;

    free_tree_helper(n);
}

void free_tree_helper(node *n)
{
    // Free all children of this node in post-order traversal
    node *child = n->firstChild;
    while(child)
    {
        // Save the next sibling pointer to avoid dangling pointers
        node *next = child->nextSibling;
        free_tree_helper(child);
        child = next;
    }

    // All the children have been freed, now free the parent
    free(n->name);
    free(n->text);
    free(n);
}

Alternatively, if you use a memory pool to allocate your tree nodes, all of your nodes come from the same pool, and the pool contains no other tree's nodes, you can instead just free the entire memory pool at once, saving you from having to traverse the entire tree. This will be much more efficient, since it avoids a lot of cache misses in a potentially large tree, and it also avoids certain memory fragmentation problems.

Upvotes: 0

Related Questions