free n-ary tree

This is a discussion on free n-ary tree within the C Programming forums, part of the General Programming Boards category; I'm having a hard time trying to free an N-ary tree, don't know if this is asking too much, but ...

  1. #1
    Registered User Tiago's Avatar
    Join Date
    Oct 2009
    Location
    Lisbon, Portugal
    Posts
    28

    free n-ary tree

    I'm having a hard time trying to free an N-ary tree, don't know if this is asking too much, but can somebody please post a small and fast algorithm for that? or at least give me some guidelines...

    thank you

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Have you tried freeing it in the reverse order of how it was malloc'ed?

    Think of the malloc'd nodes as if you pushed them onto a stack. (FILO). Now you want to pop them off that stack, and free them.

    If you're still stuck, post up your code and tell us what has you stumped. My shirt pocket appears not to have an example of this, at this time.

  3. #3
    Registered User
    Join Date
    Aug 2003
    Posts
    1,197
    Recursion should do the trick:
    Code:
    clearNode(Node *n)
    {
        int i=0;
        while(i < N) 
        {
            if(n->leaf[i])
            {
                clearNode(n->leaf[i]);
                free(n->leaf[i]);
            }
            i++;
        }
        free(n);
    }
    Or something along that line.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    Well since we've already got a code solution posted. I'll show a simpler alternative. However it intentionally contains at least two hidden bugs (so you still have to take the time to debug it if you wish to use it).
    Code:
    void freeTree(Node *n)
    {
        if (n == NULL)
            return;
        for (int i=0; i<N; ++i);
            freeTree(n->child[1]);
        free(n);
    }
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User Tiago's Avatar
    Join Date
    Oct 2009
    Location
    Lisbon, Portugal
    Posts
    28
    Done! Quite simple actually... ty

    Code:
    void freeTree(Tree_str *Tree){
    	if(Tree){
    		freeTree(Tree->brother);
    		freeTree(Tree->son);
    		free(Tree);
    	}
    }

  6. #6
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Do an in-order traversal deleting only leaves. You will have to create a temporary place holder for the next in-order node* before you delete it (because you cannot find the next in-order node for one that does not exist), which with a leaf that will be it's parent, and that parent will at some point end up as a leaf at which point it gets deleted.

    Make sense? I promise it does work.

    * alternately, you can do this recursively, but recursion is less efficient and prone to stack overflows on large trees. I just noticed that was your post above, which is recursive...this is a limitation!
    Last edited by MK27; 05-30-2010 at 02:50 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 04:15 PM
  2. Tree Problem
    By recluse in forum C Programming
    Replies: 36
    Last Post: 12-04-2004, 02:06 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  5. binary tree node structure
    By Kirsten in forum C Programming
    Replies: 2
    Last Post: 04-26-2002, 08:02 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21