/************************ BST.java ************************** * generic binary search tree */

public class BST> { protected BSTNode root = null; public BST() { } public void clear() { root = null; } public boolean isEmpty() { return root == null; } public void insert(T el) { BSTNode p = root, prev = null; while (p != null) { // find a place for inserting new node; prev = p; if (el.compareTo(p.el) (el); else if (el.compareTo(prev.el) (el); else prev.right = new BSTNode(el); } public void recInsert(T el) { root = recInsert(root,el); } protected BSTNode recInsert(BSTNode p, T el) { if (p == null) p = new BSTNode(el); else if (el.compareTo(p.el) p = root; while (p != null) if (el.equals(p.el)) return p.el; else if (el.compareTo(p.el) p) { System.out.print(p.el + " "); } protected void inorder(BSTNode p) { if (p != null) { inorder(p.left); visit(p); inorder(p.right); } } protected void preorder(BSTNode p) { if (p != null) { visit(p); preorder(p.left); preorder(p.right); } } protected void postorder(BSTNode p) { if (p != null) { postorder(p.left); postorder(p.right); visit(p); } } public void deleteByCopying(T el) { BSTNode node, p = root, prev = null; while (p != null && !p.el.equals(el)) { // find the node p prev = p; // with element el; if (el.compareTo(p.el) tmp = node.left; // node has both children; BSTNode previous = node; // 1. while (tmp.right != null) { // 2. find the rightmost previous = tmp; // position in the tmp = tmp.right; // left subtree of node; } node.el = tmp.el; // 3. overwrite the reference // to the element being deleted; if (previous == node) // if node's left child's previous.left = tmp.left; // right subtree is null; else previous.right = tmp.left; // 4. } if (p == root) root = node; else if (prev.left == p) prev.left = node; else prev.right = node; } else if (root != null) System.out.println("el " + el + " is not in the tree"); else System.out.println("the tree is empty"); } public void deleteByMerging(T el) { BSTNode tmp, node, p = root, prev = null; while (p != null && !p.el.equals(el)) { // find the node p prev = p; // with element el; if (el.compareTo(p.el) p = root; Stack> travStack = new Stack>(); if (p != null) { travStack.push(p); while (!travStack.isEmpty()) { p = travStack.pop(); visit(p); if (p.right != null) travStack.push(p.right); if (p.left != null) // left child pushed after right travStack.push(p.left);// to be on the top of the stack; } } } public void iterativeInorder() { BSTNode p = root; Stack> travStack = new Stack>(); while (p != null) { while(p != null) { // stack the right child (if any) if (p.right != null) // and the node itself when going travStack.push(p.right); // to the left; travStack.push(p); p = p.left; } p = travStack.pop(); // pop a node with no left child while (!travStack.isEmpty() && p.right == null) { // visit it and all visit(p); // nodes with no right child; p = travStack.pop(); } visit(p); // visit also the first node with if (!travStack.isEmpty()) // a right child (if any); p = travStack.pop(); else p = null; } } public void iterativePostorder2() { BSTNode p = root; Stack> travStack = new Stack>(), output = new Stack>(); if (p != null) { // left-to-right postorder = right-to-left preorder; travStack.push(p); while (!travStack.isEmpty()) { p = travStack.pop(); output.push(p); if (p.left != null) travStack.push(p.left); if (p.right != null) travStack.push(p.right); } while (!output.isEmpty()) { p = output.pop(); visit(p); } } } public void iterativePostorder() { BSTNode p = root, q = root; Stack> travStack = new Stack>(); while (p != null) { for ( ; p.left != null; p = p.left) travStack.push(p); while (p != null && (p.right == null || p.right == q)) { visit(p); q = p; if (travStack.isEmpty()) return; p = travStack.pop(); } travStack.push(p); p = p.right; } } public void breadthFirst() { BSTNode p = root; Queue> queue = new Queue>(); if (p != null) { queue.enqueue(p); while (!queue.isEmpty()) { p = queue.dequeue(); visit(p); if (p.left != null) queue.enqueue(p.left); if (p.right != null) queue.enqueue(p.right); } } } public void MorrisInorder() { BSTNode p = root, tmp; while (p != null) if (p.left == null) { visit(p); p = p.right; } else { tmp = p.left; while (tmp.right != null && // go to the rightmost node of tmp.right != p) // the left subtree or tmp = tmp.right; // to the temporary parent of p; if (tmp.right == null) {// if 'true' rightmost node was tmp.right = p; // reached, make it a temporary p = p.left; // parent of the current root, } else { // else a temporary parent has been visit(p); // found; visit node p and then cut tmp.right = null; // the right pointer of the current p = p.right; // parent, whereby it ceases to be } // a parent; } } public void MorrisPreorder() { BSTNode p = root, tmp; while (p != null) { if (p.left == null) { visit(p); p = p.right; } else { tmp = p.left; while (tmp.right != null && // go to the rightmost node of tmp.right != p) // the left subtree or tmp = tmp.right; // to the temporary parent of p; if (tmp.right == null) {// if 'true' rightmost node was visit(p); // reached, visit the root and tmp.right = p; // make the rightmost node a temporary p = p.left; // parent of the current root, } else { // else a temporary parent has been tmp.right = null; // found; cut the right pointer of p = p.right; // the current parent, whereby it ceases } // to be a parent; } } } public void MorrisPostorder() { BSTNode p = new BSTNode(), tmp, q, r, s; p.left = root; while (p != null) if (p.left == null) p = p.right; else { tmp = p.left; while (tmp.right != null && // go to the rightmost node of tmp.right != p) // the left subtree or tmp = tmp.right; // to the temporary parent of p; if (tmp.right == null) {// if 'true' rightmost node was tmp.right = p; // reached, make it a temporary p = p.left; // parent of the current root, } else { // else a temporary parent has been found; // process nodes between p.left (included) and p (excluded) // extended to the right in modified tree in reverse order; // the first loop descends this chain of nodes and reverses // right pointers; the second loop goes back, visits nodes, // and reverses right pointers again to restore the pointers // to their original setting; for (q = p.left, r = q.right, s = r.right; r != p; q = r, r = s, s = s.right) r.right = q; for (s = q.right; q != p.left; q.right = r, r = q, q = s, s = s.right) visit(q); visit(p.left); // visit node p.left and then cut tmp.right = null; // the right pointer of the current p = p.right; // parent, whereby it ceases to be } // a parent; } } public void balance(T data[], int first, int last) { if (first

/************************ BSTNode.java ************************** * node of a generic binary search tree */

public class BSTNode> { protected T el; protected BSTNode left, right; public BSTNode() { left = right = null; } public BSTNode(T el) { this(el,null,null); } public BSTNode(T el, BSTNode lt, BSTNode rt) { this.el = el; left = lt; right = rt; } }

*************

public class Queue { private java.util.LinkedList list = new java.util.LinkedList(); public Queue() { } public void clear() { list.clear(); } public boolean isEmpty() { return list.isEmpty(); } public T firstEl() { return list.getFirst(); } public T dequeue() { return list.removeFirst(); } public void enqueue(T el) { list.addLast(el); } public String toString() { return list.toString(); } }

**********

public class Stack { private java.util.ArrayList pool = new java.util.ArrayList(); public Stack() { } public Stack(int n) { pool.ensureCapacity(n); } public void clear() { pool.clear(); } public boolean isEmpty() { return pool.isEmpty(); } public T topEl() { if (isEmpty()) throw new java.util.EmptyStackException(); return pool.get(pool.size()-1); } public T pop() { if (isEmpty()) throw new java.util.EmptyStackException(); return pool.remove(pool.size()-1); } public void push(T el) { pool.add(el); } public String toString() { return pool.toString(); } }

*******

Question I Binary Search Trees (50 pts): Download and execute the programs related to Binary Search Trees. (class BST) Then add the following methods to the class BST.java (a) public int count() to count the number of nodes in a binary tree. (b) public boolean isLeaf(BSTNode node) to determine if a node is a leaf or not. (c) public int countLeaves() to count the number of leaves in a binary tree. (d) public int height() to find the height of a binary tree. Then write a program that creates a binary tree with random keys, traverses it using the breadth-first and depth-first (preorder, inorder, and postorder) and prints the results. 1It also tests the above methods