| 22 |
irasnyd |
1 |
// Written by Ira Snyder
|
|
|
2 |
// 11-03-2004
|
|
|
3 |
import java.io.*;
|
|
|
4 |
import java.util.*;
|
|
|
5 |
|
|
|
6 |
class UnorderedTree {
|
|
|
7 |
private Object root;
|
|
|
8 |
private Set subtrees;
|
|
|
9 |
private int size;
|
|
|
10 |
|
|
|
11 |
public UnorderedTree( ) { } //constructs an empty tree
|
|
|
12 |
|
|
|
13 |
public UnorderedTree( Object root ) { //constructs a singleton
|
|
|
14 |
this.root = root;
|
|
|
15 |
subtrees = new HashSet(); //empty set
|
|
|
16 |
size = 1;
|
|
|
17 |
}
|
|
|
18 |
|
|
|
19 |
//constructor to create any tree that is not a singleton
|
|
|
20 |
//and is not an empty tree
|
|
|
21 |
public UnorderedTree( Object root, Set trees ) {
|
|
|
22 |
this(root);
|
|
|
23 |
for( Iterator it=trees.iterator(); it.hasNext(); ) {
|
|
|
24 |
Object object = it.next();
|
|
|
25 |
if( object instanceof UnorderedTree ) {
|
|
|
26 |
UnorderedTree tree = (UnorderedTree)object;
|
|
|
27 |
subtrees.add(tree);
|
|
|
28 |
size += tree.size;
|
|
|
29 |
}
|
|
|
30 |
}
|
|
|
31 |
}
|
|
|
32 |
|
|
|
33 |
public int size( ) { return size; }
|
| 23 |
irasnyd |
34 |
|
|
|
35 |
public void printPreOrder( PrintStream ps ) {
|
|
|
36 |
printPreOrderHelper( ps, this ); //print the whole tree in preorder
|
|
|
37 |
ps.println(); //end the line
|
|
|
38 |
}
|
|
|
39 |
|
|
|
40 |
public static void printPreOrderHelper( PrintStream ps, UnorderedTree tree ) {
|
|
|
41 |
ps.print( tree.root + " " ); //print the node
|
|
|
42 |
for( Iterator it=tree.subtrees.iterator(); it.hasNext(); ) {
|
|
|
43 |
//recurse subtrees in preorder
|
|
|
44 |
printPreOrderHelper( ps, (UnorderedTree)it.next() );
|
|
|
45 |
}
|
|
|
46 |
}
|
|
|
47 |
|
|
|
48 |
public void printPostOrder( PrintStream ps ) {
|
|
|
49 |
printPostOrderHelper( ps, this ); //print the whole tree in postorder
|
|
|
50 |
ps.println(); //end the line
|
|
|
51 |
}
|
| 22 |
irasnyd |
52 |
|
| 23 |
irasnyd |
53 |
public static void printPostOrderHelper( PrintStream ps, UnorderedTree tree ) {
|
|
|
54 |
for( Iterator it=tree.subtrees.iterator(); it.hasNext(); ) {
|
|
|
55 |
//recurse subtrees in postorder
|
|
|
56 |
printPostOrderHelper( ps, (UnorderedTree)it.next() );
|
|
|
57 |
}
|
|
|
58 |
ps.print( tree.root + " "); //print the node
|
|
|
59 |
}
|
|
|
60 |
|
| 24 |
irasnyd |
61 |
public void printLevelOrder( PrintStream ps ) {
|
|
|
62 |
Queue q = new Queue();
|
| 23 |
irasnyd |
63 |
|
| 24 |
irasnyd |
64 |
q.enqueue(this); //add the root
|
|
|
65 |
|
|
|
66 |
while( !q.isEmpty() ) {
|
|
|
67 |
//remove the first item in the queue
|
|
|
68 |
UnorderedTree temp = (UnorderedTree)q.dequeue();
|
|
|
69 |
|
|
|
70 |
ps.print(temp.root + " "); //visit the node
|
|
|
71 |
|
|
|
72 |
//add all the children of temp to the queue
|
|
|
73 |
for( Iterator it=temp.subtrees.iterator(); it.hasNext(); ) {
|
|
|
74 |
q.enqueue( it.next() );
|
|
|
75 |
}
|
|
|
76 |
}
|
|
|
77 |
ps.println(); //end the current line
|
|
|
78 |
}
|
|
|
79 |
|
| 22 |
irasnyd |
80 |
} //end class UnorderedTree
|
|
|
81 |
|