Re: Tree Traversal
Mark Space wrote:
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 );
}
}