Subversion Repositories programming

Rev

Rev 25 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 25 Rev 26
Line 1... Line 1...
1 
// Written by Ira Snyder
 1 
// Written by Ira Snyder
2 
// 11-03-2004
 2 
// 11-03-2004
3 
import java.io.*;
 3 
import java.io.*;
4 
import java.util.*;
 4 
import java.util.*;
5 
 
 5 
 
- 
 
 6 
//the class UnorderedTree from pg 338+ in the book
6 
class UnorderedTree {
 7 
class UnorderedTree {
7 
	private Object root;
 8 
	private Object root;  //holds the node's data
8 
	private Set subtrees;
 9 
	private Set subtrees; //holds all of the subtrees
9 
	private int size;
 10 
	private int size;     //holds the size of the tree
10 
 
 11 
 
11 
	public UnorderedTree( ) { } //constructs an empty tree
 12 
	public UnorderedTree( ) { } //constructs an empty tree
12 
 
 13 
 
13 
	public UnorderedTree( Object root ) { //constructs a singleton
 14 
	public UnorderedTree( Object root ) { //constructs a singleton
14 
		this.root = root;
 15 
		this.root = root;
Line 17... Line 18...
17 
	}
 18 
	}
18 
 
 19 
 
19 
	//constructor to create any tree that is not a singleton
 20 
	//constructor to create any tree that is not a singleton
20 
	//and is not an empty tree
 21 
	//and is not an empty tree
21 
	public UnorderedTree( Object root, Set trees ) {
 22 
	public UnorderedTree( Object root, Set trees ) {
- 
 
 23 
		this(root); //calls "UnorderedTree( Object )" constructor
- 
 
 24 
 
- 
 
 25 
        //loops through all of the subtrees, and adds them this tree's
22 
		this(root);
 26 
        //set of subtrees
23 
		for( Iterator it=trees.iterator(); it.hasNext(); ) {
 27 
		for( Iterator it=trees.iterator(); it.hasNext(); ) {
24 
			Object object = it.next();
 28 
			Object object = it.next();
25 
			if( object instanceof UnorderedTree ) {
 29 
			if( object instanceof UnorderedTree ) {
26 
				UnorderedTree tree = (UnorderedTree)object;
 30 
				UnorderedTree tree = (UnorderedTree)object;
27 
				subtrees.add(tree);
 31 
				subtrees.add(tree);
28 
				size += tree.size;
 32 
				size += tree.size;
29 
			}
 33 
			}
30 
		}
 34 
		}
31 
	}
 35 
	}
32 
 
 36 
 
- 
 
 37 
    //returns the size of the tree
33 
	public int size( ) { return size; }
 38 
	public int size( ) { return size; }
34 
 
 39 
 
- 
 
 40 
    //prints the tree in preorder to the specified PrintStream object
35 
	public void printPreOrder( PrintStream ps ) {
 41 
	public void printPreOrder( PrintStream ps ) {
36 
		printPreOrderHelper( ps, this ); //print the whole tree in preorder
 42 
        printPreOrderHelper( ps, this ); //print the whole tree in preorder
37 
		ps.println(); //end the line
 43 
		ps.println(); //end the line
38 
	}
 44 
	}
39 
 
 45 
 
- 
 
 46 
    //a helper function to the printPreOrder() function
- 
 
 47 
    //it is what actually uses recursion
- 
 
 48 
    //
- 
 
 49 
    //The algorithm behind this is:
- 
 
 50 
    //  1. Print the current node
- 
 
 51 
    //  2. Visit all the subtrees of the current node in PreOrder
- 
 
 52 
    //
40 
	public static void printPreOrderHelper( PrintStream ps, UnorderedTree tree ) {
 53 
	private static void printPreOrderHelper( PrintStream ps, UnorderedTree tree ) {
41 
		ps.print( tree.root + " " ); //print the node
 54 
		ps.print( tree.root + " " ); //print the node
42 
		for( Iterator it=tree.subtrees.iterator(); it.hasNext(); ) {
 55 
		for( Iterator it=tree.subtrees.iterator(); it.hasNext(); ) {
43 
			//recurse subtrees in preorder
 56 
			//recurse subtrees in preorder
44 
			printPreOrderHelper( ps, (UnorderedTree)it.next() );
 57 
			printPreOrderHelper( ps, (UnorderedTree)it.next() );
45 
		}
 58 
		}
46 
	}
 59 
	}
47 
 
 60 
 
- 
 
 61 
    //prints the tree in postorder to the specified PrintStream object
48 
	public void printPostOrder( PrintStream ps ) {
 62 
	public void printPostOrder( PrintStream ps ) {
49 
		printPostOrderHelper( ps, this ); //print the whole tree in postorder
 63 
		printPostOrderHelper( ps, this ); //print the whole tree in postorder
50 
		ps.println(); //end the line
 64 
		ps.println(); //end the line
51 
	}
 65 
	}
52
66 
 
- 
 
 67 
    //a helper function for the printPostOrder() function
- 
 
 68 
    //it is what actually uses recursion to print the tree
- 
 
 69 
    //
- 
 
 70 
    //The algorithm behind this is:
- 
 
 71 
    //  1. Visit all the subtrees of the current node in PostOrder
- 
 
 72 
    //  2. Print the current node
- 
 
 73 
    //
53 
	public static void printPostOrderHelper( PrintStream ps, UnorderedTree tree ) {
 74 
	public static void printPostOrderHelper( PrintStream ps, UnorderedTree tree ) {
54 
		for( Iterator it=tree.subtrees.iterator(); it.hasNext(); ) {
 75 
		for( Iterator it=tree.subtrees.iterator(); it.hasNext(); ) {
55 
			//recurse subtrees in postorder
 76 
			//recurse subtrees in postorder
56 
			printPostOrderHelper( ps, (UnorderedTree)it.next() );
 77 
			printPostOrderHelper( ps, (UnorderedTree)it.next() );
57 
		}
 78 
		}
58 
		ps.print( tree.root + " "); //print the node
 79 
		ps.print( tree.root + " "); //print the node
59 
	}
 80 
	}
60 
 
 81 
 
- 
 
 82 
    //prints the tree in LevelOrder to the specified PrintStream object
- 
 
 83 
    //
- 
 
 84 
    //This is the algorithm (from pg 342-343 in the book):
- 
 
 85 
    //  1. Initialize a Queue
- 
 
 86 
    //  2. Add the root to the queue
- 
 
 87 
    //  3. Repeat steps 4-6 until the queue is empty
- 
 
 88 
    //  4. Remove the first node x from the queue
- 
 
 89 
    //  5. Visit x
- 
 
 90 
    //  6. Add all the children of x to the queue
- 
 
 91 
    //
61 
	public void printLevelOrder( PrintStream ps ) {
 92 
	public void printLevelOrder( PrintStream ps ) {
62 
		Queue q = new Queue();
 93 
		Queue q = new Queue();
63 
 
 94 
 
64 
		q.enqueue(this); //add the root
 95 
		q.enqueue(this); //add the root
65
96
Line 77... Line 108...
77 
		ps.println(); //end the current line
 108 
		ps.println(); //end the current line
78 
	}
 109 
	}
79 
 
 110 
 
80 
} //end class UnorderedTree
 111 
} //end class UnorderedTree
81 
 
 112 
 
82 
 
 -