Program That Uses a Binary Search Tree, Circular Linked List and Hashing Using Java Programming Language Assignment Solution.

Instructions

Objective
Write a program that uses a binary search tree, circular linked list and hashing using Java programming language.

Requirements and Specifications

Source Code

```BS TREE public class BSTree<E extends Comparable> implements BSTreeInterface<E> {     private Node<E> root;     public BSTree()     {         root = null;     }     //assumes the new node does not exist in the tree     public void insertBST(E obj)     {         Node<E> newNode = new Node<E>(obj);         if (root == null)             root = newNode;         else {             int comp = -999; //Java requires an initialization here             Node<E> lead, lag;             lead = lag = root;             while (lead != null) {                 lag = lead;                 comp = newNode.info.compareTo(lag.info);                 if (comp < 0)                     lead = lag.left;                 else                     lead = lag.right;             }             //lead fell off tree             if (comp < 0)                 lag.left = newNode;             else                 lag.right = newNode;         }     }     public E find(E obj)     {         Node<E> findNode = new Node<E>(obj);         Node<E> r = root;         int comp;         while (r != null && (comp = r.info.compareTo(findNode.info)) != 0) {             if (comp < 0)                 r = r.right;             else                 r = r.left;         }         if (r == null)             return null;         return r.info;     }     private void intrav(Node<E> r, StringBuilder sb)     {         if (r != null) {             intrav(r.left, sb);             sb.append(r.info.toString() + "\n");             intrav(r.right, sb);         }     }     public String toString()     {         StringBuilder sb = new StringBuilder();         intrav(root, sb);         return sb.toString();     } } CIRCULAR LIST public class CircularList {     private Item list;     public CircularList()     {         list = null;     }     public Boolean isEmpty()     {         return list == null;     }     public void append(int x)     {         Item r = new Item(x);         if (isEmpty()) {             r.next = r;         }         else {             r.next = list.next;             list.next = r;         }         list = r;     }     //write a new method here that returns the info of the last item in the list     //Javadoc comment required     /**      * Method, returning integer, stored int last list item or -1, if list is empty      * @return last list item data of -1 if the list is empty      */     public int getLast() {         return isEmpty() ? -1 : list.info;     }     public String toString()     {         StringBuilder s = new StringBuilder("");         if (!isEmpty()) {             Item r = list.next;             while (r != list) {                 s.append(r.info + ", ");                 r = r.next;             }             //append last item             s.append(r.info);         }         return s.toString();     } } HASH TABLE import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner; public class HashTable {     public static final int MAX = 30;     private String hashTable[];     public HashTable() throws FileNotFoundException {         hashTable = new String[MAX];         //be certain array contains all nulls         for (int i = 0; i < MAX; ++i)             hashTable[i] = null;         //read file of common words         int collisions = 0;         Scanner commonWords = new Scanner(new File("Common_words.txt"));         while (commonWords.hasNext()) {             String word = commonWords.nextLine();             //put word into hash table, handling collisions             for (int i = hash(word); ; i = (i + 1) % MAX) {                 if (hashTable[i] == null) {                     hashTable[i] = word;                     break;                 }                 collisions++;             }         }         System.out.println                 ("Number of collisions building the table: " + collisions);     }     public int hash(String word) {         char ch;         double total;         total = 0.0;         for (int i = 0; i < word.length(); ++i) {             ch = word.charAt(i);             total += (double) ch;             total *= Math.PI;         }         double decimal = total - (int) total;         int hash = (int) (MAX * decimal);         return hash;     }     public Boolean find(String word) {         //use hashing here for fast search, implement linear probing to handle collisions         for (int i = hash(word); ; i = (i + 1) % MAX) {             if (hashTable[i] == null)                 break;             if (word.equals(hashTable[i]))                 return true;         }         //this hard-coded return value is here to allow this method stub to compile         return false;     }     public String toString() {         //traverses the hash table to output each word, preceded by a word count         //this hard-coded return value is here to allow this method stub to compile         String result = "";         for (int i = 0; i < MAX; i++) {             result += ((i + 1) + " " + hashTable[i] + System.lineSeparator());         }         return result;     } }```