JAVA Problem BST A text concordance BST is a BST of all the

JAVA Problem (BST) A text concordance BST is a BST of all the distinct words in a piece of text, and in this project we consider the problem of constructing one concordance for a document stored in a file. To construct such a concordance BST, we begin with an empty BST. As each word is read, we will check the list whether it is in current BST or not. If the word is a new word, it is inserted into the BST in the appropriate place. If the word you read appears in the BST already, the frequency of the word will be increased by one. Obviously, it may be necessary to insert words at any point in this BST. Each node consists of four fields, one for word, one for its frequency, and two for right/left child link(reference) fields. Each time a word is read from a document, this BST must be searched, always beginning with the root node. (The data type of the word field would be a string. If the word starts with non-alphabet(number or special symbol) do not insert it in the list. Also the characters of all words will be upper case only without any punctuation.) ALGORITHM: (* Input : A Text file (concordinput.txt) Function : Construct a text concordance BST from a document stored in a file. Output : A list of distinct words with their frequencies in an ascending alphabetic order. *) Output • The source file should be called CONCORD • You will be expected to hand in the hard copy of your source files in a folder and output as well as upload your program to blackboard. concordinput.txt DEAR MARLIN THE AARDVARKS AND THE CAMELS WERE MISTAKENLY SHIPPED TO THE AZORES I AM A BOY YOU ARE A GIRL WE ARE SO COOL SORRY ABOUT THAT AS MY JUNIOR YEAR DRAWS TO A CLOSE I AM MORE AND MORE EAGER TO RETURN TO OUR COMPANY MY TELEPHONE NUMBER IS IN MY WEB CITE MY AGE IS 21 THOSE ARE MY FRIENDS ALEX TOM JOHN MICHAEL MICHAEL KIM THE CAMEL AND LION ARE GOOD FRIEND EACH OTHER SEE HOW TREES ARE USED TO IMPLEMENT THE FILE SYSTEM OF OTHER OPERATING SYSTEM SEE HOW TREE CAN BE USED TO IMPLEMENT DISCUSS AND USE THE TREE SYSTEM SHOW HOW TO USE TREE TO SUPPORT IN TIME AND HOW TO USE THIS IDEA AS I MENTIONED I LOVE THE COMPANY ALSO I LOVE COSC237 THANK YOU AND I AM LOOKING FORWARD TO HEARING FROM YOU SEE YOU SOON SINCERELY John

Solution

Code:

package com.chegg;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.Scanner;

public class BinarySearchTree {
   public static Node root;

   public BinarySearchTree() {
       this.root = null;
   }

   public boolean find(String s) {
       Node current = root;
       while (current != null) {
           if (current.data.equals(s)) {
               current.occurance++;
               return true;
           } else if (current.data.compareTo(s) > 0) {
               current = current.left;
           } else {
               current = current.right;
           }
       }
       return false;
   }

   public boolean delete(String s) {
       Node parent = root;
       Node current = root;
       boolean isLeftChild = false;
       while (!current.data.equals(s)) {
           parent = current;
           if (current.data.compareTo(s) > 0) {
               isLeftChild = true;
               current = current.left;
           } else {
               isLeftChild = false;
               current = current.right;
           }
           if (current == null) {
               return false;
           }
       }
       // if i am here that means we have found the node
       // Case 1: if node to be deleted has no children
       if (current.left == null && current.right == null) {
           if (current == root) {
               root = null;
           }
           if (isLeftChild == true) {
               parent.left = null;
           } else {
               parent.right = null;
           }
       }
       // Case 2 : if node to be deleted has only one child
       else if (current.right == null) {
           if (current == root) {
               root = current.left;
           } else if (isLeftChild) {
               parent.left = current.left;
           } else {
               parent.right = current.left;
           }
       } else if (current.left == null) {
           if (current == root) {
               root = current.right;
           } else if (isLeftChild) {
               parent.left = current.right;
           } else {
               parent.right = current.right;
           }
       } else if (current.left != null && current.right != null) {

           // now we have found the minimum element in the right sub tree
           Node successor = getSuccessor(current);
           if (current == root) {
               root = successor;
           } else if (isLeftChild) {
               parent.left = successor;
           } else {
               parent.right = successor;
           }
           successor.left = current.left;
       }
       return true;
   }

   public Node getSuccessor(Node deleleNode) {
       Node successsor = null;
       Node successsorParent = null;
       Node current = deleleNode.right;
       while (current != null) {
           successsorParent = successsor;
           successsor = current;
           current = current.left;
       }
       // check if successor has the right child, it cannot have left child for
       // sure
       // if it does have the right child, add it to the left of
       // successorParent.
       // successsorParent
       if (successsor != deleleNode.right) {
           successsorParent.left = successsor.right;
           successsor.right = deleleNode.right;
       }
       return successsor;
   }

   public void insert(String s) {
       if (!find(s)) {
           Node newNode = new Node(s);
           if (root == null) {
               root = newNode;
               return;
           }
           Node current = root;
           Node parent = null;
           while (true) {
               parent = current;
               if (current.data.compareTo(s) > 0) {
                   current = current.left;
                   if (current == null) {
                       parent.left = newNode;
                       return;
                   }
               } else {
                   current = current.right;
                   if (current == null) {
                       parent.right = newNode;
                       return;
                   }
               }
           }
       }
   }

   public void display(Node root) {
       if (root != null) {
           display(root.left);
           System.out.println(\" \" + root.data + \" : \" + root.occurance);
           display(root.right);
       }
   }

   public static void main(String arg[]) {
       System.out.println(\"Enter file path:\");
       Scanner sc = new Scanner(System.in);
       String filePath = sc.next();
       File file = new File(filePath);
       BinarySearchTree b = new BinarySearchTree();
       try {
           FileReader fr = new FileReader(file);
           BufferedReader br = new BufferedReader(fr);
           String line = br.readLine();
           while(line != null){
               String words[] = line.split(\" \");
               for(String s : words){
                   char c = s.charAt(0);
                   if(Character.isLetter(c))
                   b.insert(s);
               }
               line = br.readLine();
           }
       } catch (IOException e) {
           e.printStackTrace();
       }
       System.out.println(\"Original Tree : \");
       b.display(b.root);
      
   }
}

class Node{
   String data;
   int occurance;
   Node left;
   Node right;  
   public Node(String data){
       this.data = data;
       left = null;
       right = null;
       occurance = 1;
   }
}

Output:

Enter file path:
C:\\Users\\user\\Desktop\\chegg\\concordinput.txt
Original Tree :
A : 3
AARDVARKS : 1
ABOUT : 1
AGE : 1
ALEX : 1
ALSO : 1
AM : 3
AND : 6
ARE : 5
AS : 2
AZORES : 1
BE : 1
BOY : 1
CAMEL : 1
CAMELS : 1
CAN : 1
CITE : 1
CLOSE : 1
COMPANY : 2
COOL : 1
COSC237 : 1
DEAR : 1
DISCUSS : 1
DRAWS : 1
EACH : 1
EAGER : 1
FILE : 1
FORWARD : 1
FRIEND : 1
FRIENDS : 1
FROM : 1
GIRL : 1
GOOD : 1
HEARING : 1
HOW : 4
I : 6
IDEA : 1
IMPLEMENT : 2
IN : 2
IS : 2
JOHN : 1
JUNIOR : 1
John : 1
KIM : 1
LION : 1
LOOKING : 1
LOVE : 2
MARLIN : 1
MENTIONED : 1
MICHAEL : 2
MISTAKENLY : 1
MORE : 2
MY : 5
NUMBER : 1
OF : 1
OPERATING : 1
OTHER : 2
OUR : 1
RETURN : 1
SEE : 3
SHIPPED : 1
SHOW : 1
SINCERELY : 1
SO : 1
SOON : 1
SORRY : 1
SUPPORT : 1
SYSTEM : 3
TELEPHONE : 1
THANK : 1
THAT : 1
THE : 7
THIS : 1
THOSE : 1
TIME : 1
TO : 10
TOM : 1
TREE : 3
TREES : 1
USE : 3
USED : 2
WE : 1
WEB : 1
WERE : 1
YEAR : 1
YOU : 4