BinaryTree.java.html

  1  /**
  2     A binary tree in which each node has two children.
  3  */
  4  public class BinaryTree
  5  {
  6     private Node root;
  7  
  8     /**
  9        Constructs an empty tree.
 10     */
 11     public BinaryTree() { root = null; } 
 12  
 13     /**
 14        Constructs a tree with one node and no children.
 15        @param rootData the data for the root
 16     */
 17     public BinaryTree(Object rootData) 
 18     {
 19        root = new Node();
 20        root.data = rootData;
 21        root.left = null;
 22        root.right = null;
 23     }
 24  
 25     /**
 26        Constructs a binary tree.
 27        @param rootData the data for the root
 28        @param left the left subtree
 29        @param right the right subtree
 30     */
 31     public BinaryTree(Object rootData, BinaryTree left, BinaryTree right)
 32     {
 33        root = new Node();
 34        root.data = rootData;
 35        root.left = left.root;
 36        root.right = right.root;
 37     }
 38     
 39     class Node
 40     {
 41        public Object data;
 42        public Node left;
 43        public Node right;
 44     }
 45  
 46     /**
 47        Returns the height of the subtree whose root is the given node.
 48        @param n a node or null
 49        @return the height of the subtree, or 0 if n is null
 50     */
 51     private static int height(Node n)
 52     {
 53        if (n == null) { return 0; }
 54        else { return 1 + Math.max(height(n.left), height(n.right)); }
 55     }
 56  
 57     /**
 58        Returns the height of this tree.
 59        @return the height
 60     */
 61     public int height() { return height(root); }
 62  
 63     /**
 64        Checks whether this tree is empty.
 65        @return true if this tree is empty
 66     */
 67     public boolean isEmpty() { return root == null; }
 68  
 69     /**
 70        Gets the data at the root of this tree.
 71        @return the root data
 72     */
 73     public Object data() { return root.data; }
 74     
 75     /**
 76        Gets the left subtree of this tree.
 77        @return the left child of the root
 78     */
 79     public BinaryTree left() 
 80     { 
 81        BinaryTree result = new BinaryTree();
 82        result.root = root.left; 
 83        return result;
 84     }
 85  
 86     /**
 87        Gets the right subtree of this tree.
 88        @return the right child of the root
 89     */
 90     public BinaryTree right() 
 91     { 
 92        BinaryTree result = new BinaryTree();
 93        result.root = root.right; 
 94        return result;
 95     }
 96  }