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

Transcribed Image Text:

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<E> getRoot() public java.util. ArrayList<TreeNode<E>> path(E e) public boolean delete(E e) 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<E> getRoot() public java.util. ArrayList<TreeNode<E>> path(E e) public boolean delete(E e) Use the BST.java, Tree.java Submit files: BST.java, Tree.java and TestBST.java

Answer rating: 100% (QA)

Please find all the code explanations within the code itself as comments Please note that the code is implemented using the instructions given in the problem statement The assumptions made to implemen... View the full answer