Don\'t alter main() or makeRandomTree(). Declare all functions: Solution public

Question

Don't alter main() or makeRandomTree(). Declare all functions:

Explanation / Answer

public class BST { private BSTNode root; private int size; // Creats an empty BST public BST() { root = null; size = 0; } //Inserts a node into the BST public void insert(Comparable data) { root = insert(root, data); } private BSTNode insert(BSTNode p, Comparable data) { if (p == null) { size++; return new BSTNode(data); } if (p.getData().compareTo(data) == 0) return p; if (p.getData().compareTo(data) > 0) p.setLeft(insert(p.getLeft(), data)); else p.setRight(insert(p.getRight(), data)); return p; } // Returns the minimum node public BSTNode findMin() { return (root != null) ? findMinHelper(root) : null; } private BSTNode findMinHelper(BSTNode p) { return (p.getLeft() != null) ? findMinHelper(p.getLeft()) : p; } // Returns the height of the tree public int height() { return height(root); } private int height(BSTNode p) { if (p == null) return -1; else return 1+Math.max(height(p.getLeft()), height(p.getRight())); } // Counts the number of internal nodes public int internalNum() { return internalNum(root); } private int internalNum(BSTNode p) { if (p == null) return 0; else if (p.getLeft() == null && p.getRight() == null) return 0; else return 1 + internalNum(p.getLeft()) + internalNum(p.getRight()); } // Counts the number of external nodes public int externalNum() { return externalNum(root); } private int externalNum(BSTNode p) { if (p == null) return 0; else if (p.getLeft() == null && p.getRight() == null) return 1; else return externalNum(p.getLeft()) + externalNum(p.getRight()); } //Computes the number of leaves at a given depth. public int frequency(int depth) { return frequencyCount(root, depth); } private int frequencyCount(BSTNode p, int depth) { if(p == null) return 0; else if(p.getLeft() == null && p.getRight() == null && depth == 0) return 1; else { depth--; return frequencyCount(p.getLeft(), depth)+ frequencyCount(p.getRight(), depth); } } // Pre-order Traversal public void printPreOrderTraversal() { System.out.print("{"); if(root != null) preOrderHelper(root); System.out.println("}"); } private void preOrderHelper(BSTNode r) { System.out.print(r.getData()); if (r.getLeft() != null) { System.out.print(","); preOrderHelper(r.getLeft()); } if (r.getRight() != null) { System.out.print(","); preOrderHelper(r.getRight()); } } // Post-order Traversal public void printPostOrderTraversal() { System.out.print("{"); if(root != null) postOrderHelper(root); System.out.println("}"); } private void postOrderHelper(BSTNode r) { if (r.getLeft() != null) { postOrderHelper(r.getLeft()); System.out.print(","); } if (r.getRight() != null) { postOrderHelper(r.getRight()); System.out.print(","); } System.out.print(r.getData()); } // In-order Traversal public void printInOrderTraversal() { System.out.print("{"); if(root != null) inOrderHelper(root); System.out.println("}"); } private void inOrderHelper(BSTNode r) { if (r.getLeft() != null) { inOrderHelper(r.getLeft()); System.out.print(","); } System.out.print(r.getData()); if (r.getRight() != null) { System.out.print(","); inOrderHelper(r.getRight()); } } // Level-order Traversal public void printLevelOrderTraversal() { System.out.print("{"); if (root != null) levelOrderHelper(root); System.out.println("}"); } private void levelOrderHelper(BSTNode r) { int count=1; Queue Q = new Queue(); Q.enqueue(r); while (!Q.isEmpty()) { BSTNode tmp = (BSTNode) Q.dequeue(); if(tmp.getLeft() != null) Q.enqueue(tmp.getLeft()); if(tmp.getRight() != null) Q.enqueue(tmp.getRight()); System.out.print(tmp.getData()); if (count++ 0) p.setRight( delete (p.getRight(), d) ); else { size--; if (p.getLeft() == null) return p.getRight(); else if (p.getRight() == null) return p.getLeft(); else { // p is a node to be deleted // get data from the rightmost node in the left subtree BSTNode tmp = new BSTNode(retrieveData(p.getLeft())); // delete the rightmost node in the left subtree size++; tmp.setLeft( delete(p.getLeft(), tmp.getData()) ); // set the right link tmp.setRight(p.getRight()); p = tmp; } } return p; } private Comparable retrieveData(BSTNode p) { while (p.getRight() != null) p = p.getRight(); return p.getData(); } public static void main(String[] args) { BST T = new BST(); int [] A = {11,4,12,5,8,2,7,9,1,3,15,5}; for(int i=0; i

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.