Tree.java.html

  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  }