Subversion Repositories programming

// Written by Ira Snyder
// 11-03-2004
// License: Public Domain (added 07-11-2005)

import java.io.*;
import java.util.*;

//the class UnorderedTree from pg 338+ in the book
class UnorderedTree {
    private Object root;  //holds the node's data
    private Set subtrees; //holds all of the subtrees
    private int size;     //holds the size of the tree

    public UnorderedTree( ) { } //constructs an empty tree

    public UnorderedTree( Object root ) { //constructs a singleton
        this.root = root;
        subtrees = new HashSet(); //empty set
        size = 1;
    }

    //constructor to create any tree that is not a singleton
    //and is not an empty tree
    public UnorderedTree( Object root, Set trees ) {
        this(root); //calls "UnorderedTree( Object )" constructor

        //loops through all of the subtrees, and adds them this tree's
        //set of subtrees
        for( Iterator it=trees.iterator(); it.hasNext(); ) {
            Object object = it.next();
            if( object instanceof UnorderedTree ) {
                UnorderedTree tree = (UnorderedTree)object;
                subtrees.add(tree);
                size += tree.size;
            }
        }
    }

    //returns the size of the tree
    public int size( ) { return size; }

    //prints the tree in preorder to the specified PrintStream object
    public void printPreOrder( PrintStream ps ) {
        printPreOrderHelper( ps, this ); //print the whole tree in preorder
        ps.println(); //end the line
    }

    //a helper function to the printPreOrder() function
    //it is what actually uses recursion
    //
    //The algorithm behind this is:
    //  1. Print the current node
    //  2. Visit all the subtrees of the current node in PreOrder
    //
    private static void printPreOrderHelper( PrintStream ps, UnorderedTree tree ) {
        ps.print( tree.root + " " ); //print the node
        for( Iterator it=tree.subtrees.iterator(); it.hasNext(); ) {
            //recurse subtrees in preorder
            printPreOrderHelper( ps, (UnorderedTree)it.next() );
        }
    }

    //prints the tree in postorder to the specified PrintStream object
    public void printPostOrder( PrintStream ps ) {
        printPostOrderHelper( ps, this ); //print the whole tree in postorder
        ps.println(); //end the line
    }

    //a helper function for the printPostOrder() function
    //it is what actually uses recursion to print the tree
    //
    //The algorithm behind this is:
    //  1. Visit all the subtrees of the current node in PostOrder
    //  2. Print the current node
    //
    public static void printPostOrderHelper( PrintStream ps, UnorderedTree tree ) {
        for( Iterator it=tree.subtrees.iterator(); it.hasNext(); ) {
            //recurse subtrees in postorder
            printPostOrderHelper( ps, (UnorderedTree)it.next() );
        }
        ps.print( tree.root + " "); //print the node
    }

    //prints the tree in LevelOrder to the specified PrintStream object
    //
    //This is the algorithm (from pg 342-343 in the book):
    //  1. Initialize a Queue
    //  2. Add the root to the queue
    //  3. Repeat steps 4-6 until the queue is empty
    //  4. Remove the first node x from the queue
    //  5. Visit x
    //  6. Add all the children of x to the queue
    //
    public void printLevelOrder( PrintStream ps ) {
        Queue q = new Queue();

        q.enqueue(this); //add the root
        
        while( !q.isEmpty() ) {
             //remove the first item in the queue
            UnorderedTree temp = (UnorderedTree)q.dequeue();

            ps.print(temp.root + " "); //visit the node

            //add all the children of temp to the queue
            for( Iterator it=temp.subtrees.iterator(); it.hasNext(); ) {
                q.enqueue( it.next() );
            }
        }
        ps.println(); //end the current line
    }

} //end class UnorderedTree