Re: PreOrder Tree Traversal
Mark Space wrote
Jeff Higgins wrote:
I appreciate your staying with me. Thanks.
Ok, the second thing I see is your "hasNext()" itself. Here's Sedgewick's
algorithm:
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);
}
}
There's a strictly language issue in that I don't think pushing "null" and
then testing for empty stack is a great way to implement things in Java,
but let's let that slide. What I see here is a way to structure the
iterator better. Namely, looking at Sedgewick's algorithm, I see:
traverse(struct *t) // Constructor
{
stack.push(t); // Constructor
while (!stack.empty()) // Has next
{
t = stack.pop(); // Has next
visit(t); // Next
if (t-.r != z) stack.push(t->r); // Next
if (t-.l != z) stack.push(t->l); // Next
}
}
So same algorithm, just re-arrange things slightly. Here's my result:
Ok, this might be source of the seeming disconnect;
May still be my thick skull however...
I'm not iterating over BinaryTreeNodes, but Nodes as defined in my OP.
I'm traversing a tree of EdgeContainers as I've defined them in my OP.
My need is to have Nodes and Edges as separate concepts, I want to
keep them and access them separately and so far this concept is working
well.
(I was going to say except for this 'traversal problem') but indeed it
is working, (at least so far as I've tested) but now my concern has become
that I implement this tree walk with unugly code.
class Node {
String data;
}
class Edge {
Node source;
Node target;
}
class EdgeContainer {
Edge root; Edge left; Edge right;
}
And in my Tree I have a
Map<Node, EdgeContainer> nodeMap;
I 'prime' my iterator in its constructor with a Node;
because that's what I want to have back from my next();
So, if I rewrite my iterator following the template below:
class PreOrderIterator implements Iterator<Node> {
Stack<EdgeContainer> stack;
EdgeContainer current;
// fine
public PreOrderIterator(Node node) {
stack = new Stack<EdgeContainer>();
stack.push( nodeMap.get(node) );
}
// fine
@Override
public boolean hasNext() {
if( !stack.isEmpty() )
current = stack.pop();
else
current = null;
// Oops!
return current != null;
}
// Now I'm going to need a BIDIMap
// or a Map<EdgeContainer, Node>
// in addition to my Map<Node, EdgeContainer>
// to get back to my Node :(
@Override
public Node next() {
if( current.right != null )
stack.push( ? );
if( current.left != null )
stack.push( ? );
return ? ;
}
@Override
public void remove() {
throw new
UnsupportedOperationException("Not supported yet.");
}
}
This is a darn sight easier to understand I think, and has a lot less
branches than yours does.
Yes, I agree it's easier to understand, and is certainly much prettier
but I cannot understand how to shoehorn my structure into this algorithm.
It's simpler because it uses a simpler tree node structure too,
I guess this is the crux.
but I think the algorithm is simpler, period.
I hope you can see how I went from Sedgewick's algorithm to the iterator
one. Try to read both a few times if you don't. Btw, I tested the
iterator above quickly, and it seemed to work, but I can't swear there are
no bugs in it, so be careful.
This is a good skill. You should be able to translate between iterators,
non-recursive, and recursive algorithms, just by looking at one, and
writing down the steps it uses to complete it's task. That proves that
you really do understand what the computer is doing. When working on a
simple problem like this, you should stop and verify each stage before
going on to the next one, just so you don't chase down a dead end due to
some error in a previous step. Sedgewick and other references should be
very handy here.
So regarding your question "what to use besides a deque?" um, a Stack
comes to mind.
Well, here's my inexperience showing up again.
In the Javadocs for Stack they recommend I use Deque in preference
to Stack. Since this project is for the moment single threaded
I decided to use Deque rather than Stack and a Deque rather than
a LinkedList, because I don't need a get(int idx).
Also, I think part of our miscommunication was because I was only showing
you snippets of my code.
It's going to take me some time to absorb the following,
but I will follow it cause I have an interest.
Thanks
JH