Tree Traversal
I wrote the following in-order tree traversal without using recursion,
just to see if I could. It appears to work. If anyone would like to
check it to see if they can find any errors, I'd appreciate it.
No it's not homework, just a self-exercise in programming. ^_^
/*
* Traverse.java
*
* Created on August 24, 2007, 6:34 AM
* Copyright 2007. All rights reserved.
* To change this template, choose Tools | Template Manager
* and open the template in the editor.
*/
package treetraversal;
import java.util.Stack;
/**
*
* @author B
*/
public class Traverse
{
BinaryTreeNode tree;
/** 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();
t.traverseTree();
}
private void makeRandomTree()
{
for(int i = 0; i < 10; i++ )
{
BinaryTreeNode n = new BinaryTreeNode();
n.value = Math.random();
insertNode( this.tree, n );
}
}
private void insertNode( BinaryTreeNode parent, 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 traverseTree()
{
// 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 visitNode( BinaryTreeNode node )
{
System.out.println( node.value );
}
}
class BinaryTreeNode
{
public BinaryTreeNode left;
public BinaryTreeNode right;
public double value;
}