import java.util.Random; public class TreeDemo { public static void main(String[
ID: 3865284 • Letter: I
Question
import java.util.Random;
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
BinarySearchTree myTree = new BinarySearchTree(); // 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();
}
}
Program Assignment #3 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 Tres, your project will also need two other classes: 1. BinarSechTe- This will serve as your container class. It needs to have functionality for adding nodes and searching (traversing) the tree 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. 2. To submit your program, either zip all files together, or copy and paste all three into a single file and upload it to Canvas. The rubric below will be used in the grading of your program. Partial points may be awarded for each category. Category Program is free of errors and is well-commented Node class contains references to two children, the string, and the frequency of that word Successfully implement and instantiate a Binary Search Tree that holds Node objects Value New strings are successfully added to the tree in their correct position using alphabetical sorting. (If the word "Ball" is at the root, the word "Apple" would go left, but the word "Orange would go right) Strings already in the tree should not be added again; instead, the frequency should be increased Program correctly searches for and displays a node Program correctly uses Pre Order traversal to print all the nodes in the tree Program correctly uses In Order traversal to print all the nodes in the tree Program correctly uses Post Order traversal to print all the nodes in the tree 15 15 15 15 /100 Total PointsExplanation / Answer
Given below is the code and output. Please do rate the answer if it helped. Thank you.
Node.java
public class Node {
private String word;
private int frequency;
private Node left;
private Node right;
public Node(String word)
{
this.word = word;
this.frequency = 1;
}
public void incrementFrequency()
{
frequency++;
}
public int getFrequency()
{
return frequency;
}
public String getWord() {
return word;
}
public void setWord(String word) {
this.word = word;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
public void setFrequency(int frequency) {
this.frequency = frequency;
}
}
BinarySearchTree.java
public class BinarySearchTree {
private Node root;
public BinarySearchTree()
{
}
public void insert(String word)
{
if(root == null)
root = new Node(word);
else
{
Node curr = root;
while(curr != null)
{
if(curr.getWord().equals(word))
{
curr.incrementFrequency();
break;
}
else if(curr.getWord().compareTo(word) > 0)
{
if(curr.getLeft() == null) //no more left child, add the new word here
{
curr.setLeft(new Node(word));
break;
}
else
curr = curr.getLeft();
}
else
{
if(curr.getRight() == null) //no more left child, add the new word here
{
curr.setRight(new Node(word));
break;
}
else
curr = curr.getRight();
}
}
}
//System.out.println("Inserted " + word);
}
public void search(String word)
{
System.out.println("Searching " + word);
Node curr = root;
while(curr != null)
{
if(curr.getWord().equals(word))
break;
else if(curr.getWord().compareTo(word) > 0)
curr = curr.getLeft();
else
curr = curr.getRight();
}
if(curr == null)
System.out.println("Not found " + word);
else
System.out.println("Found " + word + ", Frequency = " + curr.getFrequency());
}
private void inorder(Node n)
{
if(n == null) return;
inorder(n.getLeft());
System.out.println(n.getWord() + "[" + n.getFrequency() + "]");
inorder(n.getRight());
}
public void printInOrder()
{
System.out.println("Inorder traversal");
inorder(root);
System.out.println("------");
}
private void preorder(Node n)
{
if(n == null) return;
System.out.println(n.getWord() + "[" + n.getFrequency() + "]");
preorder(n.getLeft());
preorder(n.getRight());
}
public void printPreOrder()
{
System.out.println("Preorder traversal");
preorder(root);
System.out.println("------");
}
private void postorder(Node n)
{
if(n == null) return;
postorder(n.getLeft());
postorder(n.getRight());
System.out.println(n.getWord() + "[" + n.getFrequency() + "]");
}
public void printPostOrder()
{
System.out.println("Postorder traversal");
postorder(root);
System.out.println("------");
}
}
output of TreeDemo.java
Adding: Hoyle
Adding: Levin
Adding: Looby
Adding: Looby
Adding: Naif
Adding: Amok
Adding: Hoyle
Adding: Naif
Adding: Brevet
Adding: Brevet
Adding: Kvell
Adding: Minotaur
Adding: Brevet
Adding: Brevet
Adding: Hoyle
Adding: Minotaur
Adding: Hoyle
Adding: Nirvana
Adding: Brevet
Adding: Dehort
Adding: Brevet
Adding: Dehort
Adding: Pissoir
Adding: Redact
Adding: Naif
Adding: Redact
Adding: Looby
Adding: Scion
Adding: Hoyle
Adding: Scion
---Searches---
Searching Dehort
Found Dehort, Frequency = 2
Searching Kvell
Found Kvell, Frequency = 1
Searching Kvell
Found Kvell, Frequency = 1
---Printing---
Preorder traversal
Hoyle[5]
Amok[1]
Brevet[6]
Dehort[2]
Levin[1]
Kvell[1]
Looby[3]
Naif[3]
Minotaur[2]
Nirvana[1]
Pissoir[1]
Redact[2]
Scion[2]
------
Inorder traversal
Amok[1]
Brevet[6]
Dehort[2]
Hoyle[5]
Kvell[1]
Levin[1]
Looby[3]
Minotaur[2]
Naif[3]
Nirvana[1]
Pissoir[1]
Redact[2]
Scion[2]
------
Postorder traversal
Dehort[2]
Brevet[6]
Amok[1]
Kvell[1]
Minotaur[2]
Scion[2]
Redact[2]
Pissoir[1]
Nirvana[1]
Naif[3]
Looby[3]
Levin[1]
Hoyle[5]
------
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.