Tree.java

import java.util.Collection; public interface Tree extends Collection {  /** Return true if the element is in the tree */  public boolean search(E e);   /** Insert element e into the binary tree   * Return true if the element is inserted successfully */  public boolean insert(E e);   /** Delete the specified element from the tree   * Return true if the element is deleted successfully */  public boolean delete(E e);    /** Get the number of elements in the tree */  public int getSize();    /** Inorder traversal from the root*/  public default void inorder() {  }   /** Postorder traversal from the root */  public default void postorder() {  }   /** Preorder traversal from the root */  public default void preorder() {  }    @Override /** Return true if the tree is empty */  public default boolean isEmpty() {    return this.size() == 0;  }   @Override  public default boolean contains(Object e) {    return search((E)e);  }    @Override  public default boolean add(E e) {    return insert(e);  }    @Override  public default boolean remove(Object e) {    return delete((E)e);  }    @Override  public default int size() {    return getSize();  }    @Override  public default boolean containsAll(Collection c) {    // Left as an exercise    return false;  }   @Override  public default boolean addAll(Collection c) {    // Left as an exercise    return false;  }   @Override  public default boolean removeAll(Collection c) {    // Left as an exercise    return false;  }   @Override  public default boolean retainAll(Collection c) {    // Left as an exercise    return false;  }   @Override  public default Object[] toArray() {    // Left as an exercise    return null;  }   @Override  public default  T[] toArray(T[] array) {    // Left as an exercise    return null;  } }

BST.java

public class BST implements Tree {  protected TreeNode root;  protected int size = 0;  protected java.util.Comparator c;   /** Create a default BST with a natural order comparator */  public BST() {    this.c = (e1, e2) -> ((Comparable)e1).compareTo(e2);  }   /** Create a BST with a specified comparator */  public BST(java.util.Comparator c) {    this.c = c;  }   /** Create a binary tree from an array of objects */  public BST(E[] objects) {    this.c = (e1, e2) -> ((Comparable)e1).compareTo(e2);    for (int i = 0; i < objects.length; i++)      add(objects[i]);  }   @Override /** Returns true if the element is in the tree */  public boolean search(E e) {    TreeNode current = root; // Start from the root     while (current != null) {      if (c.compare(e, current.element) < 0) {        current = current.left;      }      else if (c.compare(e, current.element) > 0) {        current = current.right;      }      else // element matches current.element        return true; // Element is found    }     return false;  }   @Override /** Insert element e into the binary tree   * Return true if the element is inserted successfully */  public boolean insert(E e) {    if (root == null)      root = createNewNode(e); // Create a new root    else {      // Locate the parent node      TreeNode parent = null;      TreeNode current = root;      while (current != null)        if (c.compare(e, current.element) < 0) {          parent = current;          current = current.left;        }        else if (c.compare(e, current.element) > 0) {          parent = current;          current = current.right;        }        else          return false; // Duplicate node not inserted       // Create the new node and attach it to the parent node      if (c.compare(e, parent.element) < 0)        parent.left = createNewNode(e);      else        parent.right = createNewNode(e);    }     size++;    return true; // Element inserted successfully  }   protected TreeNode createNewNode(E e) {    return new TreeNode<>(e);  }   @Override /** Inorder traversal from the root */  public void inorder() {    inorder(root);  }   /** Inorder traversal from a subtree */  protected void inorder(TreeNode root) {    if (root == null) return;    inorder(root.left);    System.out.print(root.element + " ");    inorder(root.right);  }   @Override /** Postorder traversal from the root */  public void postorder() {    postorder(root);  }   /** Postorder traversal from a subtree */  protected void postorder(TreeNode root) {    if (root == null) return;    postorder(root.left);    postorder(root.right);    System.out.print(root.element + " ");  }   @Override /** Preorder traversal from the root */  public void preorder() {    preorder(root);  }   /** Preorder traversal from a subtree */  protected void preorder(TreeNode root) {    if (root == null) return;    System.out.print(root.element + " ");    preorder(root.left);    preorder(root.right);  }   /** This inner class is static, because it does not access       any instance members defined in its outer class */  public static class TreeNode {    protected E element;    protected TreeNode left;    protected TreeNode right;     public TreeNode(E e) {      element = e;    }  }   @Override /** Get the number of nodes in the tree */  public int getSize() {    return size;  }   /** Returns the root of the tree */  public TreeNode getRoot() {    return root;  }   /** Returns a path from the root leading to the specified element */  public java.util.ArrayList> path(E e) {    java.util.ArrayList> list =      new java.util.ArrayList<>();    TreeNode current = root; // Start from the root     while (current != null) {      list.add(current); // Add the node to the list      if (c.compare(e, current.element) < 0) {        current = current.left;      }      else if (c.compare(e, current.element) > 0) {        current = current.right;      }      else        break;    }     return list; // Return an array list of nodes  }   @Override /** Delete an element from the binary tree.   * Return true if the element is deleted successfully   * Return false if the element is not in the tree */  public boolean delete(E e) {    // Locate the node to be deleted and also locate its parent node    TreeNode parent = null;    TreeNode current = root;    while (current != null) {      if (c.compare(e, current.element) < 0) {        parent = current;        current = current.left;      }      else if (c.compare(e, current.element) > 0) {        parent = current;        current = current.right;      }      else        break; // Element is in the tree pointed at by current    }     if (current == null)      return false; // Element is not in the tree     // Case 1: current has no left child    if (current.left == null) {      // Connect the parent with the right child of the current node      if (parent == null) {        root = current.right;      }      else {        if (c.compare(e, parent.element) < 0)          parent.left = current.right;        else          parent.right = current.right;      }    }    else {      // Case 2: The current node has a left child      // Locate the rightmost node in the left subtree of      // the current node and also its parent      TreeNode parentOfRightMost = current;      TreeNode rightMost = current.left;       while (rightMost.right != null) {        parentOfRightMost = rightMost;        rightMost = rightMost.right; // Keep going to the right      }       // Replace the element in current by the element in rightMost      current.element = rightMost.element;       // Eliminate rightmost node      if (parentOfRightMost.right == rightMost)        parentOfRightMost.right = rightMost.left;      else        // Special case: parentOfRightMost == current        parentOfRightMost.left = rightMost.left;         }     size--; // Reduce the size of the tree    return true; // Element deleted successfully  }   @Override /** Obtain an iterator. Use inorder. */  public java.util.Iterator iterator() {    return new InorderIterator();  }   // Inner class InorderIterator  private class InorderIterator implements java.util.Iterator {    // Store the elements in a list    private java.util.ArrayList list =      new java.util.ArrayList<>();    private int current = 0; // Point to the current element in list     public InorderIterator() {      inorder(); // Traverse binary tree and store elements in list    }     /** Inorder traversal from the root*/    private void inorder() {      inorder(root);    }     /** Inorder traversal from a subtree */    private void inorder(TreeNode root) {      if (root == null) return;      inorder(root.left);      list.add(root.element);      inorder(root.right);    }     @Override /** More elements for traversing? */    public boolean hasNext() {      if (current < list.size())        return true;       return false;    }     @Override /** Get the current element and move to the next */    public E next() {      return list.get(current++);    }     @Override // Remove the element returned by the last next()    public void remove() {      if (current == 0) // next() has not been called yet        throw new IllegalStateException();       delete(list.get(--current));       list.clear(); // Clear the list      inorder(); // Rebuild the list    }  }   @Override /** Remove all elements from the tree */  public void clear() {    root = null;    size = 0;  } }

Use the BST.java , Tree.java

Submit files: BST.java, Tree.java and TestBST.java

The task of this project is to complete all necessary methods of BST class. Modify BST class to implement the following new methods(: Tree height method to calculate height of BST at any given point of implements ** Returns the height of this binary tree */ public int height() - Breadth First Traversal to traverse and print nodes of the tree ** Displays the nodes in a breadth-first traversal */ public void breadthFirst Traversal() - Leaf count: Add new method to count and retum the number of leaf nodes: ** Returns the number of leaf nodes */ public int getNumberOfLeaves() Nonleaves count: add new method to count and return the number of nonleaf nodes ** Returns the number of nonleaf nodes */ public int getNumberofNonLeaves() Inorder traversal without using recursion. Implement inorder method in BST using stack instead of recursion. ** print tree nodes in inorder traversal */ public void nonRecursivelnorder () postorder traversal without using recursion. Implement inorder method in BST using stack instead of recursion. ** print tree nodes in inorder traversal */ public void nonRecursivepostorder () preorder traversal without using recursion. Implement inorder method in BST using stack instead of recursion. ** print tree nodes in inorder traversal */ public void nonRecursivepreorder() Create TestBST class to all new methods and methods listed below. Test with Tree with String nodes and then Integer nodes. Insert between 10-15 tree nodes. - public boolean search(E e) - public boolcan insert(E e) - public TreeNode getRoot() public java.util. ArrayList path(E e) public boolean delete(E e) Use the BST.java, Tree.java Submit files: BST.java, Tree.java and TestBST.java