Re: Iterating through an n-ary tree


"Ben Pfaff" <blp@xxxxxxxxxxxxxxx> wrote in message
news:87d584whu2.fsf@xxxxxxxxxxxxxxxxxxx
"Oliver Wong" <owong@xxxxxxxxxxxxxx> writes:

I'm sort of embarassed that this one seems to have me stumped. I want
to
write an iterator which will iterate through all the nodes (internal and
leaves) of a given n-ary tree. The order of iteration doesn't really
matter
(though I figure the easiest solution will produce either postfix or
prefix), as long as every node is returned exactly once. I'm not supposed
to
modify the tree while iterating through it. I don't think this matters,
but
I'll be coding the solution in Java.

Multiple solutions are described at:
http://adtinfo.org/libavl.html/Traversing-a-BST.html
(This is my website.)

Thanks. I read the site, and some of the algorithms there are very
interesting (e.g. the "up-and-left" versus "up-and-right" trick described in
"Better Iterative Traversal"). Unfortunately, they seem to assume a binary
search tree, whereas I have an n-ary tree, with arbitrary ordering of the
nodes (in fact, the nodes cannot be said to be ordered in any meaningful
way, as this is actually an abstract syntax tree from parsing source code).

- Oliver


.

Relevant Pages

  • Re: Iterating through an n-ary tree
    ... modify the tree while iterating through it. ... Slightly trickier, but still pretty easy, would be to have the iterator ... internally keep a stack representing the current position in the tree. ... As far as I know there is no way to traverse a tree, binary or n-ary, ...
    (comp.programming)
  • Re: PreOrder Tree Traversal
    ... If your not going through a class, try the wikipedia entries on tree ... Normally recursive means the algorithm calls itself. ... don't use recursion.", had me wondering for some time. ... You can't use recursion with iterator because you have ...
    (comp.lang.java.help)
  • Re: Iterating through an n-ary tree
    ... supposed to modify the tree while iterating through it. ... there's an specific interface in Java which I'm trying ... Returns an iterator over a set of elements of type T. ... I'm trying to get my n-ary tree to implement this interface. ...
    (comp.programming)
  • Re: PreOrder Tree Traversal
    ... Stack<BinaryTreeNode> stack; ... stack.push(tree); ... I 'prime' my iterator in its constructor with a Node; ...
    (comp.lang.java.help)
  • Re: Iterating through an n-ary tree
    ... write an iterator which will iterate through all the nodes (internal and ... supposed to modify the tree while iterating through it. ... proc walktree(root as tree, walkproc as procedure, args as whatever) ...
    (comp.programming)