+1 (315) 557-6473 

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


Instructions

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

Requirements and Specifications

program that uses binary search tree circular linked list and hashing Java programming language
program that uses binary search tree circular linked list and hashing Java programming language 1
program that uses binary search tree circular linked list and hashing Java programming language 2
program that uses binary search tree circular linked list and hashing Java programming language 3
program that uses binary search tree circular linked list and hashing Java programming language 4

Source Code

BS TREE

public class BSTree implements BSTreeInterface

{

    private Node root;

    public BSTree()

    {

        root = null;

    }

    //assumes the new node does not exist in the tree

    public void insertBST(E obj)

    {

        Node newNode = new Node(obj);

        if (root == null)

            root = newNode;

        else {

            int comp = -999; //Java requires an initialization here

            Node 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 findNode = new Node(obj);

        Node 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 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;

    }

}