Tree Traversal

Discussion in 'Java' started by Mark Space, Aug 24, 2007.

  1. Mark Space

    Mark Space Guest

    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;
    }
    Mark Space, Aug 24, 2007
    #1
    1. Advertising

  2. Mark Space

    Jeff Higgins Guest

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

    }
    Jeff Higgins, Aug 25, 2007
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. ebrian
    Replies:
    0
    Views:
    321
    ebrian
    Feb 20, 2007
  2. Replies:
    9
    Views:
    4,877
  3. Replies:
    4
    Views:
    9,337
    Kaz Kylheku
    Feb 15, 2008
  4. Vijay Meena
    Replies:
    1
    Views:
    1,915
    red floyd
    Nov 30, 2008
  5. Krypto
    Replies:
    16
    Views:
    3,068
    Tim Rentsch
    Jan 21, 2009
Loading...

Share This Page