[LAD] multi branch tree in c

[Bill White]

-----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 Deutsch-Waite-Schorr
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
1-ary 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 n-ary 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 c-lab.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 push-down stack.  But, the
| elegant solution is to write a recursive function to visit nodes in the
| desired order.  That way the call-return stack serves as an implicit
| push-down stack.
|
| For a depth-first 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-----