This is my binarySearchTree class. I need to read in a simple text file to make
ID: 3835620 • Letter: T
Question
This is my binarySearchTree class. I need to read in a simple text file to make a work fequency histogram
public class BinarySearchTree {
private class Node {
private String key;
private int counter;
private Node left;
private Node right;
public Node(String node) {
key = node;
counter = 1;
left = null;
right = null;
}
}
private Node root;
BinarySearchTree() {
root = null;
}
public void insert(String key) {
root = insert(root, key);
}
public Node insert(Node root, String key) {
if (root == null) {
root = new Node(key);
return root;
}
if (root.key.compareTo(key) == 0) {
root.counter = root.counter + 1;
return root;
}
else if (key.compareTo(root.key) < 0)
root.left = insert(root.left, key);
else
root.right = insert(root.right, key);
return root;
}
public void inorder() {
inorder(root);
}
public static void inorder(Node root) {
if (root != null) {
inorder(root.left);
System.out.println(root.key + " " + root.counter);
inorder(root.right);
}
}
public boolean search(String key) {
return search(root, key);
}
private boolean search(Node root, String key) {
if (root == null)
return false;
if (root.key == key)
return true;
if (root.key.compareTo(key) > 0)
return search(root.left, key);
return search(root.right, key);
}
public void deleteKey(String key) {
root = delete(root, key);
}
public Node delete(Node root, String key) {
if (root == null)
return root;
if (key.compareTo(root.key) < 0)
root.left = delete(root.left, key);
else if (key.compareTo(root.key) > 0)
root.right = delete(root.right, key);
else {
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
root.key = minValue(root.right);
root.right = delete(root.right, root.key);
}
return root;
}
public String minValue(Node root) {
String minValue = root.key;
while (root.left != null) {
minValue = root.left.key;
root = root.left;
}
return minValue;
}
}
Explanation / Answer
Please find my implementation.
Please let me know in case of any issue.
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
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) throws FileNotFoundException {
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();*/
Scanner sc = new Scanner(System.in);
System.out.print("Enter input file name: ");
String fileName = sc.next();
// opening file
Scanner fileScanner = new Scanner(new File(fileName));
while(fileScanner.hasNext())
tree.insert(fileScanner.next());
tree.inorder();
sc.close();
fileScanner.close();
}
}
/*
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.