1 import java.util.List;
2 import java.util.ArrayList;
3
4 /**
5 A tree in which each node has an arbitrary number of children.
6 */
7 public class Tree
8 {
9 private Node root;
10
11 class Node
12 {
13 public Object data;
14 public List<Node> children;
15
16 /**
17 Computes the size of the subtree whose root is this node.
18 @return the number of nodes in the subtree
19 */
20 public int size()
21 {
22 int sum = 0;
23 for (Node child : children) { sum = sum + child.size(); }
24 return 1 + sum;
25 }
26 }
27
28 /**
29 Constructs an empty tree.
30 */
31 public Tree()
32 {
33 root = null;
34 }
35
36 /**
37 Constructs a tree with one node and no children.
38 @param rootData the data for the root
39 */
40 public Tree(Object rootData)
41 {
42 root = new Node();
43 root.data = rootData;
44 root.children = new ArrayList<Node>();
45 }
46
47 /**
48 Adds a subtree as the last child of the root.
49 */
50 public void addSubtree(Tree subtree)
51 {
52 root.children.add(subtree.root);
53 }
54
55 /**
56 Computes the size of this tree.
57 @return the number of nodes in the tree
58 */
59 public int size()
60 {
61 if (root == null) { return 0; }
62 else { return root.size(); }
63 }
64
65 // Additional methods will be added in later sections.
66 }