Re: PreOrder Tree Traversal
Jeff Higgins wrote:
Mark Space wrote
iterator better. Namely, looking at Sedgewick's algorithm, I see:
traverse(struct *t) // 1 Constructor
{ // 2
stack.push(t); // 3 Constructor
while (!stack.empty()) // 4 Has next
{ // 5
t = stack.pop(); // 6 Has next
visit(t); // 7 Next
if (t-.r != z) stack.push(t->r); // 8 Next
if (t-.l != z) stack.push(t->l); // 9 Next
}
}
So same algorithm, just re-arrange things slightly. Here's my result:
I re-wrote my version. I think this is better for a general purpose
iterator.
class PreOrderIterator implements Iterator<BinaryTreeNode> {
Stack<BinaryTreeNode> stack;
public PreOrderIterator() {
stack = new Stack<BinaryTreeNode>();
if( tree != null ) {
stack.push( tree );
}
}
@Override
public boolean hasNext() {
return !stack.isEmpty();
}
@Override
public BinaryTreeNode next() {
BinaryTreeNode current;
if ( !stack.isEmpty() ) {
current = stack.pop();
if (current.right != null) {
stack.push(current.right);
}
if (current.left != null) {
stack.push(current.left);
}
return current;
}
else
throw new NoSuchElementException();
}
@Override
public void remove() {
throw new
UnsupportedOperationException("Not supported yet.");
}
}
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;
.. get rid of the next line for the new version:
// EdgeContainer current;
// fine
public PreOrderIterator(Node node) {
stack = new Stack<EdgeContainer>();
// new code
if( node != null )
stack.push( nodeMap.get(node) );
}
// fine
@Override
public boolean hasNext() {
if( !stack.isEmpty() )
current = stack.pop();
else
current = null;
// Oops!
// I don't see the oops... anyway:
return stack.isEmpty();
// is all you need now
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() {
Start at line 4 (I added line numbers above) and do the same thing:
if( !stack.isEmpty() ) // 4
{
EdgeContainer current = nodeMap.get( stack.pop() ); // 6
if( current.right != null )
{
stack.push( current.right.target ); // 8
}
if( current.left != null )
{
stack.push( current.right.target ); // 9
}
// I'm actually not sure but maybe...
return current.root.source; // 7
// or where ever you store the current node
}
else
throw new NoSuchElementException();
}
@Override
public void remove() {
throw new
UnsupportedOperationException("Not supported yet.");
}
}
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 actually missed that. I'll check it out, thanks.