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 }