Write in Java. You will be making a binary search tree class. Then you will use
ID: 3828910 • 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
Hi, Please find my implementation.
public class BinarySearchTree {
class Node {
String key;
int freq;
Node left, right;
public Node(String item) {
key = item;
freq = 1;
left = right = null;
}
}
// Root of BST
Node root;
// Constructor
BinarySearchTree() {
root = null;
}
// This method mainly calls insertRec()
void insert(String key) {
root = insertRec(root, key);
}
/* A recursive function to insert a new key in BST */
Node insertRec(Node root, String key) {
/* If the tree is empty, return a new node */
if (root == null) {
root = new Node(key);
return root;
}
if(root.key.compareTo(key) == 0){
root.freq = root.freq + 1;
return root;
}
/* Otherwise, recur down the tree */
else if (key.compareTo(root.key) < 0)
root.left = insertRec(root.left, key);
else
root.right = insertRec(root.right, key);
/* return the (unchanged) node pointer */
return root;
}
// This method mainly calls InorderRec()
void inorder() {
inorderRec(root);
}
// A utility function to do inorder traversal of BST
void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.println(root.key+" "+root.freq);
inorderRec(root.right);
}
}
public boolean search(String key){
return searchUtil(root, key);
}
// A utility function to search a given key in BST
private boolean searchUtil(Node root, String key)
{
// Base Cases: root is null or key is present at root
if (root==null)
return false;
if (root.key==key)
return true;
// val is greater than root's key
if (root.key.compareTo(key) > 0)
return searchUtil(root.left, key);
// val is less than root's key
return searchUtil(root.right, key);
}
// This method mainly calls deleteRec()
void deleteKey(String key)
{
root = deleteRec(root, key);
}
/* A recursive function to insert a new key in BST */
Node deleteRec(Node root, String key)
{
/* Base Case: If the tree is empty */
if (root == null) return root;
/* Otherwise, recur down the tree */
if (key.compareTo(root.key) < 0)
root.left = deleteRec(root.left, key);
else if (key.compareTo(root.key) > 0)
root.right = deleteRec(root.right, key);
// if key is same as root's key, then This is the node
// to be deleted
else
{
// node with only one child or no child
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
// node with two children: Get the inorder successor (smallest
// in the right subtree)
root.key = minValue(root.right);
// Delete the inorder successor
root.right = deleteRec(root.right, root.key);
}
return root;
}
String minValue(Node root)
{
String minv = root.key;
while (root.left != null)
{
minv = root.left.key;
root = root.left;
}
return minv;
}
// Driver Program to test above functions
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
tree.insert("a");
tree.insert("sentence");
tree.insert("because");
tree.insert("a");
tree.insert("example");
tree.insert("good");
tree.insert("sentence");
tree.insert("makes");
tree.insert("a");
tree.insert("repeats");
tree.insert("sentence");
tree.insert("makes");
// print inorder traversal of the BST
tree.inorder();
}
}
/*
Sample run:
a 3
because 1
example 1
good 1
makes 2
repeats 1
sentence 3
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.