Re: PreOrder Tree Traversal
Mark Space wrote:
Jeff Higgins wrote:
Mark, thanks for the pointers. Give me some time to
digest this, I've followed your pointers to some
online sources and need some time to sort it all out.
Ok, I've had time to refresh and here are my conclusions.
I think my presentation of the problem
may have been less than clear, thanks for your patience. :-)
If I get stuck, and become frustrated with a particular piece
of code; I shall not exacerbate the situation by spending even more
time and energy running for help, I'll just take a break, relax,
and have a fresher look. I've known that for a long time but, well..
If your not going through a class, try the wikipedia entries on tree
traversal. It's a pretty basic problem in computer science and also
should be in any beginning textbook on algorithms.
Actually, that was what I had been working from. Now your comment
reminds me of my copy of Sedgewick, Algorithms in C++, one of my
all time favorite cs books, along with Scott, Programming Language
Pragmatics, sitting on a shelf not 10 feet behind me, geesh..
Is the way I'm attempting this recursive? I guess
it is in the sense that I'm recursivly calling next()
through hasNext()?
That should be "iterativly calling".
I don't think so. Normally recursive means the algorithm calls itself.
next() would have to call hasNext() in turn for this to be recursive.
I didn't think so either but your comment:
"Try looking up some other tree walk algorithms, espcially those that
don't use recursion.", had me wondering for some time. I certainly didn't
want to load up my JVM stack with a whole tree!
The classic recursive algorithm is:
void preOrder( Tree tree )
{
if( tree == null )
return;
visit( tree );
preOrder( tree.left );
preOrder( tree.right );
}
It calls itself. You can't use recursion with iterator because you have
to return to the caller, so the iterator can't use this method of
traversal.
Yes, yes and yes. This is where my presentation, and my understanding
failed.
I am(was) building an \iterator\. The algorithm texts all present it as
a traversal \function\. From my Sedgewick,
(I really need to purchase his new Java edition)
traverse(struct *t)
{
stack.push(t);
while (!stack.empty())
{
t = stack.pop(); visit(t);
if (t-.r != z) stack.push(t->r);
if (t-.l != z) stack.push(t->l);
}
}
I have a \class\ PreOrderIterator implements Iterator
that I construct an instance of with a Node argument
(not necessarily the root of my tree) and then use to
iterate over, traverse, visit the nodes of, etc. my
tree from that point.
Recursion is also very inefficient, so it's not a great idea in production
code anyway.
If there's anyone out there that doesn't have enough to be thankful for..
Jeff Higgins is not writing code to keep heavy self-propelled vehicles
airborne, afloat, or otherwise on a straight course.
Your money and children are safe. That's in the public domain
so no need to feel guilty about being thankful for it. :-)
"visit" a node means to do whatever work you want to do to each node. In
your case, it would just print out the data in the node.
I was struggling with the concepts of
visiting vs. traversing vs.iterating over.
Now I see visiting implies a pause, tea and crumpets.
When I do this:
while(iterator.hasNext()) {
System.out.print(iterator.next().toString()); }
I am iterating over my tree, because I'm using an iterator.
My hasNext() method is providing the traversal function
and I am visiting the current node through my iterators'
next() method. (more to come on this)
This isn't the whole picture of what I'm attempting.
The structure I am envisioning is a binary tree,
but I think it may be a lopsided one (?). It will
be shaped like my file system. I also want multiple
edges and quick access to a node and its edges, hence
I figured. I think there may be better ways of doing this, rather than
forcing the data into a tree.
Now see? I wish I hadn't done that. The reason I interjected that
was because I had an idea that my use of an edge container had some
bearing on how the traversal algorithm worked. Silly me.
Just because it looks like a tree, doesn't mean you should implement one.
You'll have to do some performance testing though to determine what's
best.
It's gonna be a tree if it wants to or not! :-)
and, I need to get it runnin' first. :-)
For example, consider just using the hash map. Put the full string into
each node, like "\A\B\F" instead of trying to store each little string
individually, and hash on that full string. Get the whole thing in one
look up. Should be faster than trying to recurse a tree.
The tree is not recused! ;)
A map of paths? I expect to use some (probably smallish) maps of paths
in my grand design but not feasible for my main data model. Also how
would I get the paths into the map witout building a tree?
Now, as promised, and if you're still with me and have interest.
From upthread you said:
"Even this seems too complicated to me. You might try to simplify your
algorithm here. It seems to me you could do this with out any stack at
all (and a deque seems overkill to me also)."
Are there unneccessary conditionals here,
unnecessary stack manipulations, is the
structure wrong in some way,
if not a Deque what?
public class PreOrderIterator implements Iterator<Node> {
Deque<Node> stack = new ArrayDeque<Node>();
public PreOrderIterator(Node target) {
if (target != null) { // targe's not null go ahead
stack.push(target); } }
@Override
public boolean hasNext() {
if (!stack.isEmpty()) {
EdgeContainer edge = nodeMap.get(stack.pop());
if (edge.left != null) {
if (edge.right != null) {
stack.push(edge.right.target); }
stack.push(edge.left.target);
return true; }
else if (edge.right != null) {
stack.push(edge.right.target);
return true; }
else if(edge.left == null && edge.right == null) {
if(!stack.isEmpty())
return true;
return false; }
else {
return false; }
} return false; } // stack's empty nothin left to process
@Override
public Node next() {
if (stack.isEmpty())
throw new NoSuchElementException();
return stack.peek(); }