Tree.java.html

  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  }