Purpose: I.Wam upyour Java programning skills 2. Understand the structure and ap
ID: 2247212 • Letter: P
Question
Purpose: I.Wam upyour Java programning skills 2. Understand the structure and application of a binary search tree. Task Description Your program should read from the standard input a sequence of integer values, with each value separated by a space. Your task is to: Build a binary search tree using these values in the order they are entered Print 3 traversals: pre-, in-, and post-order Allow the user to insert/delete a value. Once a new tree is generated, print it in-order. Find predecessor of a given value. The predecessor is the node that appears right before the given value in an in-order traversal. Find successor of a given value. The successor is the node that appears right after the given value in an in-order traversal. In your BST implementation, the add and delete methods must be implemented using recursion. You will lose major points for using a non-recursive implementation Note that no duplicates are allowed in this BST. Your program should use an interactive interface with the format shown below (the user inputs are underlined):Explanation / Answer
Executable Java Code:
package bstprogram;
import java.util.Scanner;
public class BSTProgram {
class BSTNode
{
int val;
BSTNode BSTlchild,BSTrchild;
public BSTNode(int v)
{
val=v;
BSTlchild=null;
BSTrchild=null;
}
}
BSTNode BSTroot;
public BSTProgram()
{
BSTroot=null;
}
void BSTaddNode(int val)
{
if(BSTSearch(val)!=null)
{
System.out.println("Already exist ignore");
return;
}
BSTroot=BSTaddingNode(BSTroot,val);
}
BSTNode BSTaddingNode(BSTNode BSTroot,int val)
{
if (BSTroot == null)
{
BSTroot = new BSTNode(val);
return BSTroot;
}
if (val < BSTroot.val)
BSTroot.BSTlchild = BSTaddingNode(BSTroot.BSTlchild, val);
else if (val > BSTroot.val)
BSTroot.BSTrchild = BSTaddingNode(BSTroot.BSTrchild, val);
return BSTroot;
}
void BSTdeleteNode(int val)
{
if(BSTSearch(val)==null)
{
System.out.println("Not exist ignore");
return;
}
BSTroot=BSTdeletingNode(BSTroot,val);
}
BSTNode BSTdeletingNode(BSTNode BSTroot,int val)
{
if (BSTroot == null)
return BSTroot;
if (val < BSTroot.val)
BSTroot.BSTlchild = BSTdeletingNode(BSTroot.BSTlchild, val);
else if (val > BSTroot.val)
BSTroot.BSTrchild = BSTdeletingNode(BSTroot.BSTrchild, val);
else
{
if (BSTroot.BSTlchild == null)
return BSTroot.BSTrchild;
else if (BSTroot.BSTrchild == null)
return BSTroot.BSTlchild;
BSTroot.val = findSuccessor(BSTroot);
BSTroot.BSTrchild = BSTdeletingNode(BSTroot.BSTrchild, BSTroot.val);
}
return BSTroot;
}
public BSTNode BSTSearch(int val) {
BSTNode node = BSTroot;
while (node != null && node.val!=val) {
if (val < node.val) {
node = node.BSTlchild;
} else if (val > node.val) {
node = node.BSTrchild;
}
}
return node;
}
int findBSTSuccessor(int val)
{
BSTNode no=BSTSearch(val);
return findSuccessor(no);
}
int findSuccessor(BSTNode BSTroot)
{
BSTroot=BSTroot.BSTrchild;
int succ = BSTroot.val;
while (BSTroot.BSTlchild != null)
{
succ = BSTroot.BSTlchild.val;
BSTroot = BSTroot.BSTlchild;
}
return succ;
}
int findBSTPredecessor(int val)
{
BSTNode no=BSTSearch(val);
return findPredecessor(no);
}
int findPredecessor(BSTNode BSTroot)
{
BSTroot=BSTroot.BSTlchild;
int pre = BSTroot.val;
while (BSTroot.BSTrchild != null)
{
pre = BSTroot.BSTrchild.val;
BSTroot = BSTroot.BSTrchild;
}
return pre;
}
void inOrder()
{
inOrderTraversal(BSTroot);
}
void inOrderTraversal(BSTNode BSTroot)
{
if (BSTroot != null)
{
inOrderTraversal(BSTroot.BSTlchild);
System.out.print(BSTroot.val + " ");
inOrderTraversal(BSTroot.BSTrchild);
}
}
void preOrder()
{
preOrderTraversal(BSTroot);
}
void preOrderTraversal(BSTNode BSTroot)
{
if (BSTroot != null)
{
System.out.print(BSTroot.val + " ");
inOrderTraversal(BSTroot.BSTlchild);
inOrderTraversal(BSTroot.BSTrchild);
}
}
void postOrder()
{
postOrderTraversal(BSTroot);
}
void postOrderTraversal(BSTNode BSTroot)
{
if (BSTroot != null)
{
inOrderTraversal(BSTroot.BSTlchild);
inOrderTraversal(BSTroot.BSTrchild);
System.out.print(BSTroot.val + " ");
}
}
public static void main(String[] args) {
BSTProgram tree = new BSTProgram();
String lin;
Scanner sc=new Scanner(System.in);
System.out.println("Please enter the initial sequence of values:");
lin=sc.nextLine();
String[] sarr = lin.split(" ");
int[] arr = new int[sarr.length];
int di=0;
for(di = 0; di < sarr.length; di++) {
arr[di] = Integer.parseInt(sarr[di]);
}
for(int k=0;k<di;k++)
tree.BSTaddNode(arr[k]);
System.out.print("Pre-Order: ");
tree.preOrder();
System.out.println();
System.out.print("In-Order: ");
tree.inOrder();
System.out.println();
System.out.print("Post-Order: ");
tree.postOrder();
System.out.println();
String command;
System.out.print("Command? ");
command=sc.nextLine();
System.out.println(command);
String[] ar=new String[10];
int val;
while(command!="E")
{
char co=command.charAt(0);
switch(co)
{
case 'I':
ar=command.split(" ");
val=Integer.parseInt(ar[1]);
tree.BSTaddNode(val);
System.out.print("In-Order: ");
tree.inOrder();
System.out.println();
break;
case 'D':
ar=command.split(" ");
val=Integer.parseInt(ar[1]);
tree.BSTdeleteNode(val);
System.out.print("In-Order: ");
tree.inOrder();
System.out.println();
break;
case 'P':
ar=command.split(" ");
val=Integer.parseInt(ar[1]);
tree.findBSTPredecessor(val);
break;
case 'S':
ar=command.split(" ");
val=Integer.parseInt(ar[1]);
tree.findBSTSuccessor(val);
break;
case 'E':break;
case 'H': System.out.println("I Insert a value");
System.out.println("D Delete a value");
System.out.println("P Find predecessor");
System.out.println("S Find successor");
System.out.println("E Exit the program");
System.out.println("H Display the message");
break;
}
System.out.print("Command? ");
command=sc.nextLine();
}
}
}
Output:
run:
Please enter the initial sequence of values:
51 29 68 90 36 40 22 59 44 99 77 60 27 83 15 75 3
Pre-Order: 51 3 15 22 27 29 36 40 44 59 60 68 75 77 83 90 99
In-Order: 3 15 22 27 29 36 40 44 51 59 60 68 75 77 83 90 99
Post-Order: 3 15 22 27 29 36 40 44 59 60 68 75 77 83 90 99 51
Command? H
H
I Insert a value
D Delete a value
P Find predecessor
S Find successor
E Exit the program
H Display the message
Command? I 88
In-Order: 3 15 22 27 29 36 40 44 51 59 60 68 75 77 83 88 90 99
Command? I 42
In-Order: 3 15 22 27 29 36 40 42 44 51 59 60 68 75 77 83 88 90 99
Command? I 22
22
Already exist ignore
In-Order: 3 15 22 27 29 36 40 42 44 51 59 60 68 75 77 83 88 90 99
Command? D 44
In-Order: 3 15 22 27 29 36 40 42 51 59 60 68 75 77 83 88 90 99
Command?
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.