Tree Traversal

[Mark Space]

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

 

[Jeff Higgins]

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. ^_^

prints true
where english-words.20 is from scowl-6.zip
<http://wordlist.sourceforge.net/>

/*
* 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.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
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)
{
List<String> words;
List<String> shuffledWords;
List<String> unShuffledWords;

Traverse t = new Traverse();
words = t.makeWordList();
shuffledWords = t.makeWordList();
Collections.shuffle(shuffledWords);
t.makeRandomTree(shuffledWords);
unShuffledWords = t.traverseTree();
if(words.size() == unShuffledWords.size())
{
boolean test = true;
for(int idx = 0; idx < words.size(); idx++)
{
if(words.get(idx).compareTo(unShuffledWords.get(idx)) != 0)
{
System.out.println("False at index " + idx);
test = false;
}
}
System.out.println(test);
}
}

private void makeRandomTree(List<String> lst)
{
for(String str : lst)
{
BinaryTreeNode n = new BinaryTreeNode();
n.value = str;
insertNode( this.tree, n );
}
}

private List<String> makeWordList()
{
BufferedReader buf;
List<String> ret = null;
try
{
buf = new BufferedReader(new FileReader("english-words.20"));
ret = new ArrayList<String>();
String tmp;
while((tmp = buf.readLine()) != null)
{
ret.add(tmp);
}
}
catch (FileNotFoundException e)
{
e.printStackTrace();
}
catch (IOException e)
{
e.printStackTrace();
}
return ret;
}

private void insertNode( BinaryTreeNode parent, BinaryTreeNode node )
{
if( this.tree == null )
this.tree = node;
else
{
BinaryTreeNode n = this.tree;
while(true)
{
if( node.value.compareTo(n.value) < 0 )
{
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 List<String> traverseTree()
{
// In-order tree traversal, with out using recursion

BinaryTreeNode node = tree;
BinaryTreeNode temp = null;
Stack<BinaryTreeNode> nodeStack = new Stack<BinaryTreeNode>();
List<String> ret = new ArrayList<String>();

// 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 null;
left_node:
while(true)
{
while( node.left != null )
{
temp = node;
node = node.left;
nodeStack.push(temp);

}

visit_current:
while(true)
{
ret.add(node.value);

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;
}
}
}
}
return ret;
}

private void visitNode( BinaryTreeNode node )
{
System.out.println( node.value );
}

}