1 import java.util.Iterator;
2 import java.util.List;
3 import java.util.LinkedList;
4 import java.util.Queue;
5
6 /**
7 A tree in which each node has an arbitrary number of children.
8 */
9 public class Tree
10 {
11 private Node root;
12
13 class Node
14 {
15 public Object data;
16 public List<Node> children;
17
18 /**
19 Computes the size of the subtree whose root is this node.
20 @return the number of nodes in the subtree
21 */
22 public int size()
23 {
24 int sum = 0;
25 for (Node child : children) { sum = sum + child.size(); }
26 return 1 + sum;
27 }
28 }
29
30 /**
31 Constructs an empty tree.
32 */
33 public Tree()
34 {
35 root = null;
36 }
37
38 /**
39 Constructs a tree with one node and no children.
40 @param rootData the data for the root
41 */
42 public Tree(Object rootData)
43 {
44 root = new Node();
45 root.data = rootData;
46 root.children = new LinkedList<Node>();
47 }
48
49 /**
50 Adds a subtree as the last child of the root.
51 */
52 public void addSubtree(Tree subtree)
53 {
54 root.children.add(subtree.root);
55 }
56
57 /**
58 Computes the size of this tree.
59 @return the number of nodes in the tree
60 */
61 public int size()
62 {
63 if (root == null) { return 0; }
64 else { return root.size(); }
65 }
66
67 /**
68 A visitor whose visit method is called for each visited node
69 during a tree traversal.
70 */
71 public interface Visitor
72 {
73 /**
74 This method is called for each visited node.
75 @param data the data of the node
76 */
77 void visit(Object data);
78 }
79
80 /**
81 Traverses this tree in preorder.
82 @param v the visitor to be invoked at each node
83 */
84 public void preorder(Visitor v) { preorder(root, v); }
85
86 /**
87 Traverses the tree with a given root in preorder.
88 @param n the root of the tree
89 @param v the visitor to be invoked at each node
90 */
91 private static void preorder(Node n, Visitor v)
92 {
93 if (n == null) { return; }
94 v.visit(n.data);
95 for (Node c : n.children) { preorder(c, v); }
96 }
97
98 /**
99 Traverses this tree in postorder.
100 @param v the visitor to be invoked at each node
101 */
102 public void postorder(Visitor v) { postorder(root, v); }
103
104 /**
105 Traverses the tree with a given root in postorder.
106 @param n the root of the tree
107 @param v the visitor to be invoked at each node
108 */
109 private static void postorder(Node n, Visitor v)
110 {
111 if (n == null) { return; }
112 v.visit(n.data);
113 for (Node c : n.children) { postorder(c, v); }
114 }
115
116 /**
117 This iterator visits the nodes of a tree in
118 breadth-first order.
119 */
120 class BreadthFirstIterator implements Iterator
121 {
122 private Queue<Node> q;
123
124 /**
125 Constructs an iterator for a given tree.
126 @param root the root of the tree
127 */
128 public BreadthFirstIterator(Node root)
129 {
130 q = new LinkedList<Node>();
131 if (root != null) { q.add(root); }
132 }
133
134 public boolean hasNext() { return q.size() > 0; }
135
136 public Object next()
137 {
138 Node n = q.remove();
139 for (Node c : n.children) { q.add(c); }
140 return n.data;
141 }
142
143 public void remove() { throw new UnsupportedOperationException(); }
144 }
145
146 public Iterator iterator()
147 {
148 return new BreadthFirstIterator(root);
149 }
150 }