[LAD] multi branch tree in c

Bill White bill.white at griggsinst.com
Mon Jul 14 15:09:44 UTC 2008

Hash: SHA1

With binary trees, with right and left daughter pointers,
you can replace null right daughter pointers with the
node's in-order successor, and null left daughter pointers
with the node's in-order predecessor.  These are called
threads.  You need to keep one bit per pointer to tell
if it's a link or a thread.   Then you can go backwards
and forwards in the tree with almost no extra space.

This generalizes to n-ary trees, but I don't remember quite
how right off the top of my head.

Julien Claassen wrote:
| Thanks David! I jst implemented the structure today and it works fine. But an
| additional question:
| Is there a way, with that tree structure only, to go through it like this:
| root next1 next11 next111
| root next1 next11 next112
| ...
| root nextN nextN2 nextN21
| root nextN nextN2 nextN22
|    I thought of using an additional list to perform this kind of action
|    Some further explanation: I need that kind of tree to realize the storage of
| LSCP commands word by word. and the above described "walk" would print out all
| available commands.
|    What I'm doing is "rsampler" a readline based frontend understanding just
| LSCP commands at the moment. I plan to do a bit more, but that's for the
| future.
|    Kindest regards
|           Julien
| --------
| Music was my first love and it will be my last (John Miles)
| ======== FIND MY WEB-PROJECT AT: ========
| http://ltsb.sourceforge.net
| the Linux TextBased Studio guide
| ======= AND MY PERSONAL PAGES AT: =======
| http://www.juliencoder.de
| _______________________________________________
| Linux-audio-dev mailing list
| Linux-audio-dev at lists.linuxaudio.org
| http://lists.linuxaudio.org/mailman/listinfo/linux-audio-dev

Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org


More information about the Linux-audio-dev mailing list