Instructions Write a program allows the user to enter and search for strings. Wh
ID: 3761302 • Letter: I
Question
Instructions
Write a program allows the user to enter and search for strings. When strings are added to the tree, they should be wrapped inside a node object that holds the string, the frequency (number of times) with which that string has been added to the tree, and references to two other nodes (children). The strings must be stored in a Binary Search Tree. You will need to implement your own Binary Search Tree (you may use the one we covered in class as a starting point). A driver has been provided for you (TreeDemo.java). You must use that class as your driver, without alterations. Be sure to analyze the driver code (specifically the methods and manner in which the methods are called) to be sure that your program functions properly.
In addition to the provided TreeDemo class, your project will also need two other classes:
1. BinarySearchTree – This will serve as your container class. It needs to have functionality for adding nodes and searching (traversing) the tree.
2. Node – Your Binary Search Tree will be made up of Node objects. Each node object must reference two children and also contain the string entered by the user and the frequency of that string.
Have to implement own Binary search tree, not use the one built into Java
Explanation / Answer
public class BinarySearchTree {
Node root;
public void insert(String data) {
Node newNode = new Node(data);
if (root == null) {
root = newNode;
} else {
Node focusNode = root;
Node parent;
while (true) {
parent = focusNode;
if (data.compareTo(focusNode.data) < 0) {
focusNode = focusNode.leftChild;
if (focusNode == null) {
parent.leftChild = newNode;
return;
}
} else {
focusNode = focusNode.rightChild;
if (focusNode == null) {
parent.rightChild = newNode;
return;
}
}
}
}
}
public void printInOrder() {
System.out.println("In order: ");
printInOrder(root);
System.out.println();
}
public void printPreOrder() {
System.out.println("Pre order: ");
printPreOrder(root);
System.out.println();
}
public void printPostOrder() {
System.out.println("Post order: ");
printPostOrder(root);
System.out.println();
}
public void printInOrder(Node focusNode) {
if (focusNode != null) {
printInOrder(focusNode.leftChild);
System.out.print(focusNode);
printInOrder(focusNode.rightChild);
}
}
public void printPreOrder(Node focusNode) {
if (focusNode != null) {
System.out.print(focusNode);
printPreOrder(focusNode.leftChild);
printPreOrder(focusNode.rightChild);
}
}
public void printPostOrder(Node focusNode) {
if (focusNode != null) {
printPostOrder(focusNode.leftChild);
printPostOrder(focusNode.rightChild);
System.out.print(focusNode);
}
}
public void search(String data) {
Node focusNode = root;
while (!focusNode.data.equals(data)) {
if (data.compareTo(focusNode.data) < 0) {
focusNode = focusNode.leftChild;
} else {
focusNode = focusNode.rightChild;
}
if (focusNode == null)
System.out.println("Not found");
}
System.out.println("Node found: "+focusNode);
}
}
class Node {
String data;
Node leftChild;
Node rightChild;
Node(String data) {
this.data = data;
}
public String toString() {
return data+" ";
}
}