[LAD] multi branch tree in c

[Jack O'Quin]

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);
}


-- 
 joq