Write in Java. You will be making a binary search tree class. Then you will use
ID: 3835501 • Letter: W
Question
Write in Java.
You will be making a binary search tree class. Then you will use it to import a text file and create a word frequency histogram.
Your binary search tree class should have the following methods:
• search—finds and returns the node that matches a search key (if it exists; otherwise return null)
• insert—inserts a node into the tree
• delete—deletes a node from the tree
• print—traverse (inorder) and print each node
• any methods you need to solve the problem of using a tree to make a word frequency histogram. You should be able to read a file and add a word if it isn’t in the tree yet and update a counter associated with it if it is in the tree.
Example:
Input: This sentence repeats words because a sentence that repeats words makes a good example sentence.
Output:
a 2
because 1
example 1
good 1
makes 1
repeats 2
sentence 3
that 1
this 1
words 2
Explanation / Answer
/**
* generic bianry tree node
*/
/**
* @author Sam
*
*/
class Node<T> { // very simple generic node class
T data;
Node<T> left;
Node<T> right;
public Node(T data) {
this.data = data;
left = right = null;
}
}
/**
* generic binary tree
*/
/**
* @author Sam
*
*/
public class BinaryTree<T extends Comparable<T>> { //simple binary tree class that implements comparable
Node<T> head;
public void insert(T data){ // method to insert a new node
if (head == null) { //when first node is being inserted
head = new Node<>(data);
return;
}
Node<T> tmp = head;
Node<T> parent = null; //parent is the node where insertion will occur
while (tmp != null) { // Find a node where child is null
parent = tmp;
if (tmp.data.compareTo(data) <= 0)
tmp = tmp.left;
else
tmp = tmp.right;
}
if (parent.data.compareTo(data) < 0) //insert as left child or right child
parent.left = new Node<>(data);
else
parent.right = new Node<>(data);
}
public Node<T> search(T data) { //search a node with given data
Node<T> tmp = head;
while (tmp != null) {
if (tmp.data.compareTo(data) == 0) // found
return tmp;
else if (tmp.data.compareTo(data) < 0) // will be there in left subtree
tmp = tmp.left;
else //else in right subtree
tmp = tmp.right;
}
return null;
}
public void delete (T data) { //this method is very complex
if (head.data.compareTo(data) == 0) { //head of the tree should be removed
Node<T> tmp = getLeftMostParent(head.right); // find apt node to replace the head
if (tmp == null){ // head has no right child
head = head.left; //then just replace it with immediate left child
return;
}
tmp.left.left = head.left; //else replace head with target node
tmp.left.right = head.right;
head = tmp;
tmp.left = null;
}
//this part is for removal of non head componet
Node<T> targetParent = null; //extra task over here is to find the target node as well as its parent node
Node<T> target = head;
while (target != null) {
if (target.data.compareTo(data) == 0)
break;
targetParent = target;
if (target.data.compareTo(data) < 0)
target = target.left;
else
target = target.right;
}
if (target == null) // data does not exist
return;
Node<T> tmp = getLeftMostParent(target.right); //get replacement of target node
if (tmp == null) { //if no node found our target node has only feft child
if (targetParent.data.compareTo(data) < 0) //so replace the taget with its immediate left child
targetParent.left = target.left;
else
targetParent.right = target.left;
return;
}
//else replace it with tmp.left
tmp.left.left = target.left;
tmp.left.right = target.right;
if (targetParent.data.compareTo(data) < 0)
targetParent.left = tmp.left;
else
targetParent.right = tmp.left;
tmp.left = null;
}
private Node<T> getLeftMostParent(Node<T> node){ // node to find the parent of the leftmost chid
if (node == null)
return null;
while (node.left.left != null)
node = node.left;
return node;
}
@Override
public String toString() { //used while printing
return inorderTraversal(head);
}
private String inorderTraversal(Node<T> node) { //inorder traversal
if (node == null)
return "";
return inorderTraversal(node.left) + node.data.toString() + inorderTraversal(node.right);
}
}
/****************************************************************************************/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class WordCount {
static class DataStore implements Comparable<DataStore> { //inner class to hold word and count
String word;
int freq;
public DataStore(String data) {
word = data;
freq = 1;
}
@Override
public int compareTo(DataStore o) { // comapare to forced to compare only string words
return word.compareTo(o.word);
}
@Override
public String toString() { //for printing purpose
return word + " : " + freq + " ";
}
}
public static void main(String[] args) throws IOException {
BinaryTree<DataStore> tree = new BinaryTree<>();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter a sentence to count words");
for (String s : br.readLine().split(" ")) { // get input and for every word
s = s.trim(); //remove spaces if present
Node<DataStore> tmp;
DataStore newData = new DataStore(s); // create node data structure
if ((tmp = tree.search(newData)) != null) // if the word was already added to the tree
Tmp.data.freq++; //increase count
else
tree.insert(newData); //else insert the word
}
System.out.println(tree); //then print the tree
}
}
I hope this code will help you. If you need any guidance, please let me know. I shall try my best to resolve it. I have also commented the code to make things easy.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.