[LAD] multi branch tree in c
Bill White
bill.white at griggsinst.com
Mon Jul 14 15:23:15 UTC 2008
BEGIN PGP SIGNED MESSAGE
Hash: SHA1
You can also do this with no stack, but it's kind of complicated.
As you go down the tree, you can reverse the links, and then
replace them as you come back. This is called the DeutschWaiteSchorr
algorithm, and it used to be the workhorse of all garbage collection
algorithms. I don't think it's used so much today. It's really
bad for concurrent access to the trees, as the data structure is
mangled while you are traversing it.
For example, imagine a linked list, which is kind of like a
1ary tree:
~ a > b > c > d > null
Y ou traverse this by moving the links backward in numeric order:
~ a > b > c > d > null Step zero, Visit a
~ a < b c > d > null Step one. Visit b
~ a < b < c d > null Step two. Visit c
~ a < b < c < d null Step three. Visit d
The stack is the chain of pointers you have reversed.
Then you have to go backwards, setting things right again. You
can do this with nary trees, but it takes lg(n) bits in each
node to remember which links you have visited. (I think it's
lg(n) bits.) For traversing a more general graph, possibly
with cycles, you also need to know whether you have visited
a node, but sometimes the extra bits can tell you that,
depending on whether n is a power of two or not.
Jack O'Quin wrote:
 On Fri, Jul 11, 2008 at 4:14 PM, Julien Claassen <julien at clab.de> 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.

 That is called a depth first traversal.

 You can program it out yourself using a pushdown stack. But, the
 elegant solution is to write a recursive function to visit nodes in the
 desired order. That way the callreturn stack serves as an implicit
 pushdown stack.

 For a depthfirst traversal, the visit_node() function would call itself
 recursively for each subtree first, then for the next sibling, something
 like this...

 struct node {
 struct node *child;
 struct node *sibling;
 }

 void visit_node(struct node *p)
 {
 if (p>child)
 visit_node(p>child);
 process the current node;
 if (p>sibling)
 visit_node(p>sibling);
 }


BEGIN PGP SIGNATURE
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla  http://enigmail.mozdev.org
iD8DBQFIe29jTi5xeapaTM0RAgHoAJsExki1v+UQFC9INQXh9z5I7bkeGgCfVnbx
xwSViO2AFDGiq1oePr8QNmg=
=mJSd
END PGP SIGNATURE
More information about the Linuxaudiodev
mailing list