Java programing: In this assignment, you are to implement exercises 19.15, and 1
ID: 3913253 • Letter: J
Question
Java programing:
In this assignment, you are to implement exercises 19.15, and 19.16 on page 766 of the book.
You need to start with the BinaryNode.java and the BinarySearchTree.java files provided for
you in the text. I recommend that you type them instead of obtaining them from the book's
website.
In order to test your code, you need to implement a driver program for this assignment.
Your driver program must test all the methods that are provided in the BinarySearchTree
class implementation repeatedly. So, what you need to do is go into a while loop and a
switch statement within it to handle all the choices.
while quit was not selected
switch(choice)
case 1:
Insert
case 2:
find
.
.
.
default:
quit.
end switch
end while
You need to submit all three files (BinaryNode.java, BinarySearchTree.java, and the driver)
You must not make any changes to the BinaryNode.java file, but submit it anyway.
Good Luck
19.15 : Implement find , findmin and findMax recursively;
19.16: implement findkth nonrecursively , using the same technique used for a nonrecursive find.
Explanation / Answer
As per your requirement i have written code which fulfill all your requirements please follow it step by step.
BinarySearchTree.java
import java.util.*;
public class BinarySearchTree
{
class Node
{
Node parent;
String data;
Node left;
Node right;
}
private Node root;
private int sizeElement;
public BinarySearchTree()
{
sizeElement = 0;
root = null;
}
public void addMethod(String paramterText)
{
Node nodeObject = new Node();
nodeObject.data = paramterText;
sizeElement++;
if (root != null)
addMethod(nodeObject, root);
else
root = nodeObject;
}
/**
* actually here we will inserts a nodeObject below the parent
*
* @param paramToAdd
* and the node to be added
*/
private void addMethod(Node paramToAdd, Node parent) {
if (paramToAdd.data.compareTo(parent.data) < 0) {
// Here we will insert on left
if (parent.left == null) {
parent.left = paramToAdd;
paramToAdd.parent = parent;
} else {
addMethod(paramToAdd, parent.left);
}
} else {
// And later we will insert on right
if (parent.right == null)
{
parent.right = paramToAdd;
paramToAdd.parent = parent;
}
else {
addMethod(paramToAdd, parent.right);
}
}
}
public int getSizeMethod()
{
return sizeElement;
}
private Node findLeastMethod(Node nodeObject)
{
Node leastObject = nodeObject;
while (leastObject.left != null)
leastObject = leastObject.left;
return leastObject;
}
public String findMinItemMethod()
{
return findLeastMethod(root).data;
}
private Node findGreatestMethod(Node nodeObject)
{
Node greatObject = nodeObject;
while (greatObject.right != null)
greatObject = greatObject.right;
return greatObject;
}
public String findMaxItem()
{
return findGreatestMethod(root).data;
}
/* Here we will write Functions to delete data */
public void delete(String m) {
if (getSizeMethod() == 0)
System.out.println("Tree Empty");
else if (searchMethod(m) == false)
System.out.println("Sorry " + m + " is not present");
else {
root = delete(root, m);
System.out.println(m + " deleted from the tree");
sizeElement--;
}
}
private Node delete(Node root, String m) {
Node y1, y2, h;
if (root.data.equalsIgnoreCase(m)) {
Node lt, rt;
lt = root.left;
rt = root.right;
if (lt == null && rt == null)
return null;
else if (lt == null) {
y1 = rt;
return y1;
} else if (rt == null) {
y1 = lt;
return y1;
} else {
y2 = rt;
y1 = rt;
while (y1.left != null)
y1 = y1.left;
y1.left = lt;
return y2;
}
}
if (m.compareTo(root.data) < 0) {
h = delete(root.left, m);
root.left = h;
} else {
h = delete(root.right, m);
root.right = h;
;
}
return root;
}
/* Here we will write function to searchMethod for an element recursively */
private boolean searchMethod(Node qw, String valueParameter) {
boolean foundFlag = false;
while ((qw != null) && !foundFlag) {
String rightValue = qw.data;
if (valueParameter.compareTo(rightValue) < 0)
qw = qw.left;
else if (valueParameter.compareTo(rightValue) > 0)
qw = qw.right;
else {
foundFlag = true;
break;
}
foundFlag = searchMethod(qw, valueParameter);
}
return foundFlag;
}
public boolean searchMethod(String valueParameter) {
return searchMethod(root, valueParameter);
}
}// Here let it be end_of_BST_class
BinaryNodeDriver.java
import java.util.Scanner;
public class BinaryNodeDriver
{
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
// Here we will creating object of BST
BinarySearchTree bstObject = new BinarySearchTree();
//Here we will do operation up to user want to exit from the program
while(true)
{
System.out.println(" Binary Search Tree Operations");
System.out.println("1. Insert an item in the binary searchMethod tree");
System.out.println("2. Delete an item from the binary searchMethod tree");
System.out.println("3. Find for a particular item in the tree.");
System.out.println("4. Display the minimum item in the tree.");
System.out.println("5. Display the maximum item in the tree.");
System.out.println("6. Display total number of items currently present in the binary searchMethod tree.");
System.out.println("7. Quit.");
System.out.print("Enter your choice: ");
int choiceFlag = input.nextInt();
switch (choiceFlag)
{
//First of all we will write case 1 for inserting element in to the binary tree
case 1:
System.out.print("Enter integer element to insert : ");
bstObject.addMethod(input.next());
break;
//Next we will write case 2 for deleting element in to binary tree
case 2:
System.out.print("Enter integer element to delete :");
bstObject.delete(input.next());
break;
// after that we will write case 3 for find the particular element is exist in the tree or not.
case 3:
System.out.println("Enter integer element to find : ");
System.out
.println("Search result : " + bstObject.searchMethod(input.next()));
break;
//Find the minimum element in the tree
case 4:
System.out.println("Min Item in Tree : " + bstObject.findMinItemMethod());
break;
//Find the maximum element in the tree
case 5:
System.out.println("Max Item in Tree : " + bstObject.findMaxItem());
break;
//Here we will do total number of elements in the tree
case 6:
System.out.println("Total Items in Tree = " + bstObject.getSizeMethod());
break;
case 7:
break;
default:
System.out.println("Wrong Entry h ");
break;
}
if (choiceFlag == 7)
break;
}
System.out.println("Thank You!");
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.