package trees; import java.io.*; public class BinaryTree2 { Node2 head; public int height() { return height(head); } int height(Node2 node) { if (node == null) { return 0; } int hl = height(node.left); int hr = height(node.right); if (hr > hl) { return 1 + hr; } else { return 1 + hl; } } public int nodeCount() { return nodeCount(head); } int nodeCount(Node2 node) { if (node == null) { return 0; } else { return 1 + nodeCount(node.left) + nodeCount(node.right); } } public void add(char c) { if (head == null) { head = new Node2(c); } else { add(head, c); } } void add(Node2 n, char c) { if (c < n.c) { if (n.left == null) { n.left = new Node2(c); } else { add(n.left, c); } } if (n.c < c) { if (n.right == null) { n.right = new Node2(c); } else { add(n.right, c); } } } public String toString() { if (head == null) { return "()"; } return head.toString(); } /** * Draw the tree in HTML. It's easier to understand when viewed. Note: you * are not expected to learn how to write HTML for this course. */ public void draw(String fname) throws IOException { FileWriter fw = new FileWriter(fname); PrintWriter pw = new PrintWriter(fw); pw.printf("%n"); pw.printf("%n"); pw.printf("%n"); pw.printf("%n"); pw.printf("%n"); head.draw(pw); pw.printf("%n"); pw.printf("%n"); pw.close(); } /** * Determine if the character c is contained within the BTree2. */ public boolean contains(char c) { return contains(head, c); } boolean contains(Node2 node, char c) { if (node == null) { return false; } if (node.c == c) { return true; } if (c < node.c && contains(node.left, c)) { return true; } if (node.c < c && contains(node.right, c)) { return true; } return false; } public static void main(String[] args) throws Exception { BinaryTree2 bt = new BinaryTree2(); // Note that there's only one 'g' in the tree, despite // the fact that we added it twice. Each element is // unique. for (char c : new char[]{'b', 'i', 'g', 'g', 'e', 'r'}) { bt.add(c); } System.out.printf("Tree height = %d%n", bt.height()); System.out.printf("Tree node count = %d%n", bt.nodeCount()); bt.draw("tree.html"); for (char c : new char[]{'b', 'u', 'g', 's'}) { if (bt.contains(c)) { System.out.printf("Tree contains %c%n", c); } else { System.out.printf("Tree does not contain %c%n", c); } } } }