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;
}
.

Relevant Pages

  • Re: PreOrder Tree Traversal
    ... You might try to simplify your algorithm here. ... The structure I am envisioning is a binary tree, ... BinaryTreeNode curr = this.tree; ...
    (comp.lang.java.help)
  • Re: PreOrder Tree Traversal
    ... Here is Michael Abrash's algorithm, ... BinaryTreeNode curr = this.tree; ... It therefore probably is not well suited to multi-tasking and concurrent use, but it will traverse any tree with no additional memory requirement, making it highly deterministic, and also very pithy on low-memory systems. ...
    (comp.lang.java.help)
  • Re: Tree Traversal
    ... public class Traverse ... BinaryTreeNode n = new BinaryTreeNode; ... private void insertNode(BinaryTreeNode parent, BinaryTreeNode node) ... BinaryTreeNode temp = null; ...
    (comp.lang.java.programmer)