Methods to implement (MyBST): Binary Search Tree (JAVA)
Programming Language: JAVA
Provided code (MyBST):
public class MyBST >{
private TreeNode root; private int size; public MyBST(E[] array){ for(E e: array) insert(e); } public MyBST(){ } public boolean search(E element){ TreeNode current=root; while(current!=null){ if(element.compareTo(current.element) 0){ current = current.right; } else return true; } return false; } public boolean insert(E element){ if(root == null){ root = new TreeNode(element); size ++; } else { TreeNode current=root; TreeNode parent=null; while(current!=null) { if(element.compareTo(current.element) 0){ parent = current; current = current.right; } else return false; } if(element.compareTo(parent.element) current=root; int temp=0; while(current!=null){ temp += (Integer)current.element; current = current.left; } return temp; } public E getElemAtLevel_LeftBranch(int theLevel){ TreeNode current=root; int counter = 0; for(int i=1; i counter || current == null) throw new IndexOutOfBoundsException(); else { return current.element; } } public int getMax(){ TreeNode current=root; while(current.right!=null){ current = current.right; } return (Integer)current.element; } //for leaf method current.left=current.right=null public int getNumberOfLeaves(){ return getNumberOfLeaves(root); } public int getNumberOfLeaves(TreeNode current){ if( current == null ) return 0; if( current.left == null && current.right == null ) return 1; else return getNumberOfLeaves(current.left) + getNumberOfLeaves(current.right); } //Inorder traversal public void inOrder(TreeNode node){ if(node == null) return; inOrder(node.left); System.out.print(node.element + " "); inOrder(node.right); } public void inOrder(){ inOrder(root); } //Preorder traversal public void preOrder(TreeNode node){ if(node == null) return; System.out.print(node.element + " "); preOrder(node.left); preOrder(node.right); } public void preOrder(){ preOrder(root); } //Postorder traversal public void postOrder(TreeNode node){ if(node == null) return; postOrder(node.left); postOrder(node.right); System.out.print(node.element + " "); } public void postOrder(){ postOrder(root); } }
1. Write a method E parentOf(E e) that returns the parent of object e.
2. Add the following new method in MyBST .
/** Displays the nodes in a breadth-first traversal */
public void breadthFirstTraversal() /* the elements are displayed by level */
For the tree below: 44 10 88 9 22 77 99 8 11 33 66 100 55
3. Add the following new method in MyBST .
/** Returns the height of this binary tree */
public int height()
4. Write a method pathOf(TreeNode x) to display the path from the root to node x
Thanks!
10 100