Write a program in java which reads a sequence of integer values from input- val
ID: 3714150 • Letter: W
Question
Write a program in java which reads a sequence of integer values from input- values should be separated by space. This program should Build a binary search tree using these values in the order they are entered. Print it in 3 traversal methods: pre-order. In-order, and post-order. Allow the user to Add or Remove a value. Once a new tree is generated, print it in in- order traversal . NOTES . Use recursion to implement add and remove methods, otherwise you will lose points . Duplicates are NOT allowed in this BST. At the very first step after obtaining initial values check for duplicated values. In case of any duplication asks user to enter values again .Your program should use an interactive interface with the format shown in following demo example (the user inputs are underlined) % java Project 1 Please enter values: 26 34 19 12 40 51 29 44 77 60 84 1199 41 36 22 16 Duplication values are not allowed! Please enter values 26 34 19 12 40 51 29 44 77 60 84 11 941 36 22 1615 Pre-order: XXX X In-order XXX...X Post-order: XXX... X Main Menu A: Add a value R Remove a value E : Exit the program What command would like to run? Please enter a value to add: 27 In-order: XXX...X what command would like to run? Please enter a value to add: 11 11 already exists! Duplicated values are not allowed. What command would like to run? R Please enter a value to remove:12 In-order: XXX... X What command would like to run? R Please enter a value to remove: 10 10 doesn't exist What command would like to run? E Exit!Explanation / Answer
package datastructure;
import java.util.Scanner;
//Class BinarySearchTree definition
class BSTNoDuplicate
{
// Scanner class object created
static Scanner sc = new Scanner(System.in);
// Nested class Node to store node information
class Node
{
// To store data
int data;
// To point left and right child
Node leftChild, rightChild;
// Parameterized constructor
public Node(int value)
{
data = value;
leftChild = rightChild = null;
}// End of constructor
}// End of nested class
// Declares an object as root of BST
Node root;
// Default constructor definition
BSTNoDuplicate()
{
root = null;
}// End of constructor
// Method to delete a node
void deleteNode(int data)
{
root = deleteNode(root, data);
}
// Recursive helper method to insert a new key in BST
Node deleteNode(Node root, int data)
{
// Checks If the tree is empty
if (root == null)
return root;
// Otherwise, recur down the tree
// Checks if the data to delete is less than the current node data
if (data < root.data)
// Recursively calls the method with left child
root.leftChild = deleteNode(root.leftChild, data);
// Otherwise checks if the data to delete is greater than the current node data
else if (data > root.data)
// Recursively calls the method with right child
root.rightChild = deleteNode(root.rightChild, data);
// Otherwise the data is same as root's data, then this is the node to be deleted
else
{
// Checks if node with only one child or no child
if (root.leftChild == null)
// Returns the right child
return root.rightChild;
// Otherwise checks if right child is null then return left child
else if (root.rightChild == null)
return root.leftChild;
// node with two children: Get the in-order successor (smallest in the right subtree)
root.data = minValueLeftSubtree(root.rightChild);
// Delete the in-order successor
root.rightChild = deleteNode(root.rightChild, root.data);
}// End of else
// Returns the current root
return root;
}// End of method
// Method to find minimum from left subtree
int findMinimumLeftSubtree()
{
return minValueLeftSubtree(root);
}// End of method
// Method to return value
int minValueLeftSubtree(Node root)
{
// Initially stores the root data as minimum value
int minVal = root.data;
// Loots till left child is not null
while (root.leftChild != null)
{
// Stores the current left child data as minimum value
minVal = root.leftChild.data;
// Moves to left child
root = root.leftChild;
}// End of wile loop
// Returns the minimum value
return minVal;
}// End of method
// Method to insert data to BST
void insertNode(int data)
{
root = insertNode(root, data);
}// End of method
// Recursive method to insert a new data in to BST
Node insertNode(Node root, int data)
{
// Checks if the tree is empty, then return a new node
if (root == null)
{
root = new Node(data);
return root;
}// End of if condition
// Otherwise, recurse down the tree
// Checks if the data to insert is less than the current node data
if (data < root.data)
// Recursively calls the method with moving left child
root.leftChild = insertNode(root.leftChild, data);
// Otherwise checks if the data to insert is greater than the current node data
else if (data > root.data)
// Recursively calls the method with moving right child
root.rightChild = insertNode(root.rightChild, data);
// Returns the current root node
return root;
}// End of method
// Method for in order traversal
void inorderTraversal()
{
inorderTraversalNode(root);
}// End of method
// Recursive method for in order traversal of BST
void inorderTraversalNode(Node root)
{
// Checks if root is null
if (root != null)
{
// Recursively calls the method with left child movement
inorderTraversalNode(root.leftChild);
// Displays the data
System.out.print(root.data + " ");
// Recursively calls the method with right child movement
inorderTraversalNode(root.rightChild);
}// End of if condition
}// End of method
// Method for pre order traversal
void preorderTraversal()
{
preorderTraversalNode(root);
}// End of method
// Recursive method for in order traversal of BST
void preorderTraversalNode(Node root)
{
// Checks if root is null
if (root != null)
{
// Displays the data
System.out.print(root.data + " ");
// Recursively calls the method with left child movement
preorderTraversalNode(root.leftChild);
// Recursively calls the method with right child movement
preorderTraversalNode(root.rightChild);
}// End of if condition
}// End of method
// Method for post order traversal
void postorderTraversal()
{
postorderTraversalNode(root);
}// End of method
// Recursive method for post order traversal of BST
void postorderTraversalNode(Node root)
{
// Checks if root is null
if (root != null)
{
// Recursively calls the method with left child movement
postorderTraversalNode(root.leftChild);
// Recursively calls the method with right child movement
postorderTraversalNode(root.rightChild);
// Displays the data
System.out.print(root.data + " ");
}// End of if condition
}// End of method
// Method to return true if number is already available otherwise returns false
boolean checkDuplicate(int arr[], int size)
{
// Set the found status to false for not found
boolean found = false;
// Loops till size minus one times
for (int i = 0; i < size - 1; i++)
{
// Loops till size
for (int j = i+1; j < size; j++)
{
// Checks if the current index position data is equals to the next index position data
if ((arr[i] == arr[j]) && (i != j))
{
// Set the found status to true for found
found = true;
// Come out of the loop
break;
}// End of if condition
}// End of inner for loop
}// End of outer for loop
// Returns the found status
return found;
}// End of method
// Method to return true if number is already available otherwise returns false
boolean checkDuplicate(int arr[], int size, int no)
{
// Set the found status to false for not found
boolean found = false;
// Loops till size
for (int i = 0; i < size; i++)
{
// Checks if the current index position data is equals to the number to insert
if (arr[i] == no)
{
// Set the found status to true for found
found = true;
// Come out of the loop
break;
}// End of if condition
}// End of for loop
// Returns the found status
return found;
}// End of method
// Static method to display menu, accept user choice and returns use choice
static char menu()
{
// To store user choice
char choice;
// Displays menu
System.out.print(" Main Menu ");
System.out.print(" A : Add a value.");
System.out.print(" R : Remove a value.");
System.out.print(" E : Exit the program.");
// Accepts user choice
System.out.print(" What comman would you like to run? ");
sc.nextLine();
choice = sc.next().charAt(0);
// Returns user choice
return choice;
}// End of method
// main method definition
public static void main(String[] args)
{
// Creates an array to store the values entered by the user
int arrNode[] = new int[200];
int size;
int no;
// Creates an object of the BinarySearchTree
BSTNoDuplicate tree = new BSTNoDuplicate();
// Accepts initial size of the nodes
System.out.print(" Enter how many node you wants to create: ");
size = sc.nextInt();
// Loops till valid node value entered by the user
do
{
// Accepts node values
System.out.printf(" Please enter %d values: ", size);
// Loops till entered size
for(int x = 0; x < size; x++)
// Stores the data in array
arrNode[x] = sc.nextInt();
// Calls the method to check duplicate if true is returned displays error message
if(tree.checkDuplicate(arrNode, size))
System.out.printf(" Duplicate values are not allowed! please enter %d values: ", size);
// Otherwise not duplicate
else
// Come out of the loop
break;
}while(true); // End of do - while loop
// Inserts the data to BST
// Loops till entered size
for(int x = 0; x < size; x++)
// Calls the method to insert node
tree.insertNode(arrNode[x]);
// Calls the method to display pre order traversal
System.out.print(" Pre-order: ");
tree.preorderTraversal();
// Calls the method to display in order traversal
System.out.print(" In-order: ");
tree.inorderTraversal();
// Calls the method to display post order traversal
System.out.print(" Post-order: ");
tree.postorderTraversal();
// Loops till user choice is not 'e' or 'E'
do
{
// Calls the method to check user choice and calls appropriate method
switch(menu())
{
case 'a':
case 'A':
// Accept a number to insert
System.out.print(" Please enter a value to add: ");
no = sc.nextInt();
// Calls the method to check duplicate
// If returns true then display error message
if(tree.checkDuplicate(arrNode, size, no))
System.out.printf(" %d is already exists! Duplicate values are not allowed.", no);
// Otherwise no duplicate
else
{
// Calls the method to insert node
arrNode[size++] = no;
tree.insertNode(no);
// Calls the method to display in order traversal
System.out.print(" In-order: ");
tree.inorderTraversal();
}// End of else
break;
case 'r':
case 'R':
// Accept the number to delete
System.out.print(" Please enter a value to delete: ");
no = sc.nextInt();
// Calls the method to delete node
tree.deleteNode(no);
// Loops till entered size
for(int x = 0; x < size; x++)
{
// Checks if the number is found
if(arrNode[x] == no)
// Loops from found position to size
for(int y = x; y < size; y++)
// Swaps the numbers one index position previous
arrNode[y] = arrNode[y+1];
}// End of for loop
// Decrease the size by one
size--;
// Calls the method to display in order traversal
System.out.print(" In-order: ");
tree.inorderTraversal();
break;
case 'e':
case 'E':
// Close the scanner
sc.close();
System.out.print(" Exit!");
// Exit the program
System.exit(1);
default:
System.out.print(" Invalid choice!");
}// End of switch - case
}while(true); // End of do - while loop
}// End of main method
}// End of class
Sample Output:
Enter how many node you wants to create: 18
Please enter 18 values: 26 34 19 12 40 51 29 44 77 60 84 11 9 9 41 36 22 16 15
Duplicate values are not allowed! please enter 18 values:
Please enter 18 values: 26 34 19 12 40 51 29 44 77 60 84 11 9 41 36 22 16 15
Pre-order: 15 12 11 9 26 19 16 22 34 29 40 36 51 44 41 77 60 84
In-order: 9 11 12 15 16 19 22 26 29 34 36 40 41 44 51 60 77 84
Post-order: 9 11 12 16 22 19 29 36 41 44 60 84 77 51 40 34 26 15
Main Menu
A : Add a value.
R : Remove a value.
E : Exit the program.
What comman would you like to run? a
Please enter a value to add: 27
In-order: 9 11 12 15 16 19 22 26 27 29 34 36 40 41 44 51 60 77 84
Main Menu
A : Add a value.
R : Remove a value.
E : Exit the program.
What comman would you like to run? A
Please enter a value to add: 11
11 is already exists! Duplicate values are not allowed.
Main Menu
A : Add a value.
R : Remove a value.
E : Exit the program.
What comman would you like to run? R
Please enter a value to delete: 12
In-order: 9 11 15 16 19 22 26 27 29 34 36 40 41 44 51 60 77 84
Main Menu
A : Add a value.
R : Remove a value.
E : Exit the program.
What comman would you like to run? E
Exit!
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.