Hello Jack! Thanks a lot. That's what I needed. I hope to not bother the list again with audio "relatively unrelated" question for a while. 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

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

-----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 &lt;julien(a)c-lab.de&gt; 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); | } | |