Write a program allows the user to enter and search for strings. When strings ar
ID: 665585 • Letter: W
Question
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 balanced Binary Tree (not a Binary Search Tree). You will need to implement your own Binary 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:
BinaryTree – This will serve as your container class. It needs to have functionality for adding nodes and searching (traversing) the tree.
Node – Your Binary 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.
Explanation / Answer
Answer:
/******** JAVA PROGRAM FOR BINARY TREE STORE STRINGS WITH NUMBER OF OCCURRENCES*********/
import java.io.*;
import java.util.*;
//CLASS NODE
class Node
{
Object NODEkey;
int count;
Node NodeLeftChild;
Node NodeRightChild;
Node(Object key1)
{
NODEkey=key1;
count=1;
}
}
//CLASS BINARYTREE
class BinaryTree
{
Node TREEroot;
//CALL insertNewNode() TO INSERT STRING
public void insert(Object treeKey)
{
root=insertNewNode(TREEroot,treeKeey);
}
public Node insertNewNode(Node theRoot,Object theTreeKey)
{
if(theRoot==NULL)
return new Node(treeKey);
else if(theTreeKey.compareTo(theRoot.key)<0)
theRoot.NodeLeftChild=insertNewNode(theRoot.NodeLeftChild,theTreeKey);
else if(theTreeKey.compareTo(theRoot.key)>0)
theRoot.NodeRightChild=insertNewNode(theRoot.NodeRightChild,theTreeKey);
else if(theTreeKey.compareTo(theRoot.key)==0)
theRoot.count=theRoot.count++;
return theRoot;
}
//SEARCH() FOR BINARY TREE
public void Search(Object theKey)
{
searchBinaryTree(TREEroot,theKey);
}
//SERACHES THE GIVEN STRING IN THE TREE
public void searchBinaryTree(Node theRoot,Object theTreeKey)
{
if(theRoot==NULL)
System.out.println("TREE IS EMPTY");
else if(theTreeKey.compareTo(theRoot.key)<0)
searchBinaryTree(theRoot.NodeLeftChild,theTreeKey);
else if(theTreeKey.compareTo(theRoot.key)>0)
searchBinaryTree(theRoot.NodeRightChild,theTreeKey);
else if(theTreeKey.compareTo(theRoot.key)==0)
{
System.out.println("sTRING IS AVAILABLE IN THE TREE");
System.out.println("OCCURRENCES:"+theRoot.count);
}
else
S ystem.out.println("sTRING IS not AVAILABLE IN THE TREE");
}
//GET NODELEFTCHILD
public void getNodeLeftChild()
{
return this.NodeLeftchild;
}
//GET NODERIGHTCHILD
public void getNodeRightChild()
{
return this.NodeRightchild;
}
//PRORDER TRAVERSAL
public void printPreOder()
{
Treepreorder(TREEroot);
}
public void Treepreorder(Node theRoot)
{
if(theRoot!=NULL)
{
System.out.println("String:"+theRoot.key+"Occurrence:"+theRoot.count);
Treepreorder(theRoot.getNodeLeftChild());
Treepreorder(theRoot.getNodeRightChild());
}
}
//INORDER TRAVERSAL
public void printInOder()
{
Treeinorder(TREEroot);
}
public void Treeinorder(Node theRoot)
{
if(theRoot!=NULL)
{
Treeinorder(theRoot.getNodeLeftChild());
System.out.println("String:"+theRoot.key+"Occurrence:"+theRoot.count);
Treeinorder(theRoot.getNodeRightChild());
}
}
//POSTORDER TRAVERSAL
public void printPostOder()
{
Treepostorder(TREEroot);
}
public void Treepostorder(Node theRoot)
{
if(theRoot!=NULL)
{
Treepostorder(theRoot.getNodeLeftChild());
Treepostorder(theRoot.getNodeRightChild());
System.out.println("String:"+theRoot.key+"Occurrence:"+theRoot.count);
}
}
}
//DRIVER CLASS
public class TreeDemo {
public static void main(String[] args){
//Library of words to be added to the tree.
String[] words = {"Amok", "Nirvana", "Levin", "Minotaur", "Naif", "Brevet", "Dehort", "Costive", "Boffin", "Hoyle", "Scion", "Pissoir", "Looby", "Kvell", "Redact", "Pi" };
//For easier readability, swap words for numbers.
String[] numbers = {"1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14", "15", "16"};
Random rand = new Random(); // Initialize Random
BinaryTree myTree = new BinaryTree(); // Initialize the Tree (make sure your tree class is named BinarySearchTree)
for (int addLoop = 0; addLoop < 30; addLoop++){ // Loop to add items to the Tree
int r = rand.nextInt(16);
System.out.println("Adding: " + words[r]);
myTree.insert(words[r]); // Method call to the tree to insert nodes
}
System.out.println("---Searches---"); // Start multiple searches
myTree.search(words[rand.nextInt(16)]);
myTree.search(words[rand.nextInt(16)]);
myTree.search(words[rand.nextInt(16)]);
System.out.println("---Printing---"); // Print the tree using all
myTree.printPreOrder(); // three type of order
myTree.printInOrder();
myTree.printPostOrder();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.