# 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  }`