Subversion Repositories programming

Rev

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

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