mateus A mateus A - 1 month ago 7
C Question

Free all elements in a tree

I have tried to write a recursion to free all the elements in a tree. The data structure is a struct with info, a pointer to left child and a pointer to brother.

How can i free all nodes in the tree? I have tried post-order method, but I can't get it right
Thank you

The tree is NOT binary

Answer

There are two ways you can do this, recursively or iteratively.

The recursive approach is the simplest to code. You write a "free node" function that checks if the node has any descendants or siblings and calls the "free node" on each of them, then it frees the node it was called on. Performing this "free node" operation on the root node will free the entire tree.

The iterative approach does the same thing but keeps a list of nodes to free. Here's a sketch of the iterative approach:

  1. Create a list of pointers to nodes containing only the root node.
  2. Take the node at the head of the list, add all its siblings and direct children to the list of nodes, then free that node and remove it from the list.
  3. If the list is empty, stop, you are done.
  4. Go to step 2.