Re: PreOrder Tree Traversal
Jeff Higgins wrote:
I think there are a couple of issue, some with my own communication at
least. I guess I wasn't being very clear.
First, I recognize that your original program did not use recursion.
Iterators can't, I think. So I suggested that you look up non-recursive
algorithms because that's what you have already. No worries there.
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:
class PreOrderIterator implements Iterator<BinaryTreeNode> {
Stack<BinaryTreeNode> stack;
BinaryTreeNode current;
public PreOrderIterator() {
stack = new Stack<BinaryTreeNode>();
stack.push( tree );
}
@Override
public boolean hasNext() {
if( !stack.isEmpty() )
current = stack.pop();
else
current = null;
return current != null;
}
@Override
public BinaryTreeNode next() {
if( current.right != null )
stack.push(current.right);
if( current.left != null )
stack.push( current.left );
return current;
}
@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. It's simpler because it uses a simpler tree
node structure too, 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.
Also, I think part of our miscommunication was because I was only
showing you snippets of my code. Here's the whole thing. It's got a few
broken lines in the email due to wrapping that you'll have to fix up.
This is one file, you don't have to split anything up.
/*
* Traverse.java
*
* Created on August 24, 2007, 6:34 AM
*
* To change this template, choose Tools | Template Manager
* and open the template in the editor.
*/
package treetraversal;
import java.util.Iterator;
import java.util.Stack;
public class Traverse {
BinaryTreeNode tree;
private static final int NUM_ARRAY_SLOTS = 23;
/** Creates a new instance of Traverse */
public Traverse() {
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Traverse t = new Traverse();
t.makeRandomTree();
System.out.println(" == My in order traversal:");
t.myNoRecurseInOrder();
System.out.println("\n == Michael Abrash in order traversal:");
t.abrashInOrder();
System.out.println("\n == Michael Abrash in order traversal,
original algorithm:");
t.abrashOriginalInOrder();
System.out.println("\n == Morris in order traversal:");
t.morrisInOrder();
System.out.println("\n == Pre-order Iterator:");
Traverse.PreOrderIterator iter = t.new PreOrderIterator();
while( iter.hasNext() ) {
t.visitNode( iter.next() );
}
}
private void makeRandomTree() {
for (int i = 0; i < 10; i++) {
BinaryTreeNode n = new BinaryTreeNode();
n.value = Math.random();
insertNode(n);
}
}
private void insertNode(BinaryTreeNode node) {
if (this.tree == null) {
this.tree = node;
} else {
BinaryTreeNode n = this.tree;
while (true) {
if (node.value < n.value) {
if (n.left != null) {
n = n.left;
} else {
n.left = node;
break;
}
} else {
if (n.right != null) {
n = n.right;
} else {
n.right = node;
break;
}
}
}
}
}
private void myNoRecurseInOrder() {
// In-order tree traversal, with out using recursion
BinaryTreeNode node = tree;
BinaryTreeNode temp = null;
Stack<BinaryTreeNode> nodeStack = new Stack<BinaryTreeNode>();
// note: all of the while(true) loops are, effectively, not while
// loops at all. They are just place-holders for their associated
// labels. None of these while loops ever actually loop.
if (tree == null) {
return;
}
left_node:
while (true) {
while (node.left != null) {
temp = node;
node = node.left;
nodeStack.push(temp);
}
visit_current:
while (true) {
visitNode(node);
if (node.right != null) {
temp = node;
node = node.right;
nodeStack.push(temp);
continue left_node;
} else {
pop_parent:
while (true) {
if (nodeStack.isEmpty()) {
break left_node; // DONE! Exit traversal
}
temp = nodeStack.pop();
if (temp.left == node) {
node = temp;
//goto visit_current
continue visit_current;
} else {
node = temp;
// goto pop_parent
continue pop_parent;
}
}
}
}
}
}
private void abrashInOrder() {
// Micheal Abrash, Zen of graphics programming.
if (this.tree == null) {
return;
}
Stack<BinaryTreeNode> nodeStack = new Stack<BinaryTreeNode>();
BinaryTreeNode curr = this.tree;
while (true) {
while (curr.left != null) {
nodeStack.push(curr);
curr = curr.left;
}
while (true) {
visitNode(curr);
if (curr.right != null) {
curr = curr.right;
break;
}
if (!nodeStack.isEmpty()) {
curr = nodeStack.pop();
} else {
return;
}
}
}
}
private void abrashOriginalInOrder() {
// Micheal Abrash, Zen of graphics programming.
// Closer to original version.
if (this.tree == null) {
return;
}
BinaryTreeNode[] localStack = new BinaryTreeNode[NUM_ARRAY_SLOTS];
BinaryTreeNode currentNode = this.tree;
int nodeIndex = 0;
localStack[nodeIndex++] = null;
while (true) {
while (currentNode.left != null) {
localStack[nodeIndex++] = currentNode;
currentNode = currentNode.left;
}
while (true) {
visitNode(currentNode);
if (currentNode.right != null) {
currentNode = currentNode.right;
break;
}
if ((currentNode = localStack[--nodeIndex]) == null) {
return;
}
}
}
}
private void morrisInOrder() {
// J. M. Morris, "Traversing binary trees simply and cheaply"
// Information Processing Letters, December 1979
if (this.tree == null) {
return;
}
BinaryTreeNode p = tree;
while (p != null) {
if (p.left == null) {
visitNode(p);
p = p.right;
} else {
BinaryTreeNode pre = p.left;
while (pre.right != null && pre.right != p) {
pre = pre.right;
}
if (pre.right == null) {
pre.right = p;
p = p.left;
} else {
pre.right = null;
visitNode(p);
p = p.right;
}
}
}
}
private void visitNode(BinaryTreeNode node) {
System.out.println(node.value);
}
class PreOrderIterator implements Iterator<BinaryTreeNode> {
Stack<BinaryTreeNode> stack;
BinaryTreeNode current;
public PreOrderIterator() {
stack = new Stack<BinaryTreeNode>();
stack.push( tree );
}
@Override
public boolean hasNext() {
if( !stack.isEmpty() )
current = stack.pop();
else
current = null;
return current != null;
}
@Override
public BinaryTreeNode next() {
if( current.right != null )
stack.push(current.right);
if( current.left != null )
stack.push( current.left );
return current;
}
@Override
public void remove() {
throw new
UnsupportedOperationException("Not supported yet.");
}
}
}
class BinaryTreeNode {
public BinaryTreeNode left;
public BinaryTreeNode right;
public double value;
}