Subversion Repositories programming

// Written by Ira Snyder

// 11-03-2004

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