Please show that the code is working at the end. Your program should read from the standard input...
Please show that the code is working at the end.
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):
% java Project3
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: X X X ... X
In-order: X X X ... X
Post-order: X X X ... X
Command? H
Homework Answers
solution
output
//copyable
code
// BST.java
import java.util.Scanner;
public class BST {
static Scanner in;
private static void displayMessage() {
System.out.println("I\tInsert a value");
System.out.println("D\tDelete a value");
System.out.println("P\tFind predecessor");
System.out.println("S\tFind successor");
System.out.println("E\tExit Code");
System.out.println("H\tDisplay This Message");
}
private static int get_Menu_Choice() {
System.out.print("\nCommand ? ");
return in.next().charAt(0);
}
public static void main(String[] args) {
in = new Scanner(System.in);
Binary_Search_Tree t1 = new Binary_Search_Tree();
t1.insert(51);
t1.insert(29);
t1.insert(68);
t1.insert(90);
t1.insert(36);
t1.insert(40);
t1.insert(22);
t1.insert(59);
t1.insert(44);
t1.insert(99);
t1.insert(77);
t1.insert(60);
t1.insert(27);
t1.insert(83);
t1.insert(15);
t1.insert(75);
t1.insert(3);
// BST
t1.in_order();
t1.post_order();
t1.pre_order();
while(true)
switch(get_Menu_Choice()) {
case 'I':
t1.insert(in.nextInt());
t1.in_order();
break;
case 'D':
t1.delete(in.nextInt());
t1.in_order();
break;
case 'P':
System.out.println("Predecessor : "+t1.find_Predecessor(in.nextInt()));
break;
case 'S':
System.out.println("Successor : "+t1.findSuccessor(in.nextInt()));
break;
case 'E':
System.exit(0);
case 'H':
displayMessage();
break;
default:
System.out.println("Invalid!!!");
}
}
}
class Binary_Search_Tree {
Node root;
class Node {
int datavalue;
Node leftside;
Node rightside;
Node(int datavalue) {
this.datavalue = datavalue;
}
private int find_Min() {
if (root.leftside == null)
return root.datavalue;
else
return root.leftside.find_Min();
}
}
// Constructor
Binary_Search_Tree() {
root = null;
}
//INSERT
void insert(int datavalue) {
root = insert(root, datavalue);
}
Node insert(Node root, int datavalue) {
if (root == null) {
root = new Node(datavalue);
return root;
}
// recurion down the tree
if (datavalue < root.datavalue)
root.leftside = insert(root.leftside, datavalue);
else if (datavalue > root.datavalue)
root.rightside = insert(root.rightside, datavalue);
else {
System.out.println("Duplicate Key : "+datavalue);
}
// return the (unchanged) node pointer
return root;
}
void delete(int datavalue) {
root = delete(root, datavalue);
}
Node delete(Node root, int datavalue) {
if (root == null) {
System.out.println(datavalue+" doesn't exist in the tree");
return null;
}
if (datavalue < root.datavalue)
root.leftside = delete(root.leftside, datavalue);
else if (datavalue > root.datavalue)
root.rightside = delete(root.rightside, datavalue);
else {
System.out.println("Deleted Key : "+datavalue);
root = delete(root);
}
// return
return root;
}
private Node delete(Node root) {
if(isLeaf(root)) {
return null;
} else if(root.leftside == null) {
root = root.rightside;
return root;
} else if(root.rightside == null) {
root = root.leftside;
return root;
} else {
int min = root.rightside.find_Min();
root.datavalue = min;
root.rightside = delete(root.rightside, min);
return root;
}
}
//in_order
public void in_order() {
System.out.println("In Order :");
in_order(root);
System.out.println();
}
private void in_order(Node root) {
if (root != null) {
in_order(root.leftside); // leftside
System.out.print(" "+root.datavalue); // root
in_order(root.rightside); // rightside
}
}
public void pre_order() {
System.out.println("Pre Order :");
pre_order(root);
System.out.println();
}
//pre_order
private void pre_order(Node root) {
if (root != null) {
System.out.print(" "+root.datavalue); // root
in_order(root.leftside); // leftside
in_order(root.rightside); // rightside
}
}
//post_order
public void post_order() {
System.out.println("Post Order :");
post_order(root);
System.out.println();
}
//post order
private void post_order(Node root) {
if (root != null) {
in_order(root.leftside); // leftside
in_order(root.rightside); // rightside
System.out.print(" "+root.datavalue); // root
}
}
//leaf
public boolean isLeaf(Node node) {
return node.leftside == null && node.rightside == null;
}
//predecessor
int find_Predecessor(int datavalue) {
int predecessor = -1;
return find_Predecessor(root, datavalue, predecessor);
}
private int find_Predecessor(Node root, int datavalue, int predecessor) {
if(root == null) return predecessor;
if (root.datavalue == datavalue) {
if (root.leftside != null) {
Node t = root.leftside;
while (t.rightside != null) {
t = t.rightside;
}
predecessor = t.datavalue;
}
} else if (root.datavalue < datavalue) {
predecessor = find_Predecessor(root.rightside, datavalue, root.datavalue);
} else if (root.datavalue > datavalue) {
predecessor = find_Predecessor(root.leftside, datavalue, predecessor);
}
return predecessor;
}
//successor
int findSuccessor(int datavalue) {
int successor = -1;
return findSuccessor(root, datavalue, successor);
}
private int findSuccessor(Node root, int datavalue, int successor) {
if(root == null) return successor;
if (root.datavalue == datavalue) {
if (root.rightside != null) {
Node t = root.rightside;
while (t.leftside != null) {
t = t.leftside;
}
successor = t.datavalue;
}
} else if (root.datavalue > datavalue) {
successor = findSuccessor(root.leftside, datavalue, root.datavalue);
} else if (root.datavalue < datavalue) {
successor = findSuccessor(root.rightside, datavalue, successor);
}
return successor;
}
}
Add Answer to:
Please show that the code is working at the end. Your program should read from the standard input...
using java to write,show me the output. please write some common. You CAN NOT use inbuild...
using java to write,show me the output. please write some
common.
You CAN NOT use inbuild functions for Tree ADT operations.
using code below to finsih
public class Main
{
public static void main(String[] args) {
BinaryTree tree = new
BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
tree.root.left.left.left = new Node(8);
tree.root.left.left .right= new Node(9);...
Consider the AVL Tree built by inserting the following sequence of integers, one at a time:...
Consider the AVL Tree built by inserting the following sequence of integers, one at a time: 5, 2, 8, 7,9 Then we insert 11. After we insert 11, before we perform any necessary rotations, is the tree balanced? And if not, which is the root of the lowest imbalanced subtree? (a) None, since the tree is already balanced after inserting 11. (b) The node containing 5. (c) The node containing 8. (d) The node containing 11. (e) The node containing...
please solve this question: Write a character Max-Heap Builder program in C++. The program should display...
please solve this question:
Write a character Max-Heap Builder program in C++. The program should display the menu below. Each item in the menu should be implemented in a function. a. Add a node. One node to be added to the max-heap. b. Delete a node. One node to be deleted from the max-heap. C. Search a node. Returns true if the node exists in the max-heap, otherwise it returns false. d. Print the tree. Prints the heap in level-order...
Using JAVA Lab Exercises 1. Complete the class AVLTree that extends BST. It should have four...
Using JAVA
Lab Exercises 1. Complete the class AVLTree that extends BST. It should have four methods RotateLeft, Rotate Right RotateLeftRight, and RetateRightLeft. You have to provide the methods rotate Right(), rotateLeftRight and rotateRightLeft, Provide the method delete() to delete elements in the AVL tree. 2. Create an AVL tree in which the following keys are inserted in the given order: 8, 12, 14, 18, 20, 23, 15, 13, 7, 16 Then ask the user to provide any 3 elements...
Assignment on Java programing 1. Write programs for the following exercises in Java. Each file should...
Assignment on Java programing 1. Write programs for the following exercises in Java. Each file should have short description of the implemented class and for files with main method the problem it is solving. Make sure your files have appropriate names. Programs should write output to the Console. b) BST: Implement Binary Search Tree ADT with insert(int key), delete(int key), Node find(int key), and in-order traverse() where it prints the value of the key. Your operations should use recursion. The...
please use java application to solve methods: 5,6,10,12,13 (no need for the rest) Problem1: Create a...
please use java application to solve methods:
5,6,10,12,13 (no need for the rest)
Problem1: Create a new Java Application that has the following methods: 6 A method that generate a binary search tree (BST) where the number of nodes and the range of the values are 1. from a file. 2. A recursive method to print the BST in preorder traversal 3. A recursive method to print the BST in post-order traversal 4. A recursive method to print the BST...
Would appreciate the answer in the Java coding language please and thank you! 10d 10h left...
Would appreciate the answer in the Java coding language please
and thank you!
10d 10h left Java 7 1. Check the Structure Autocomplete Ready 1 > import java.io.*;... 10 ALL A binary tree uses a multi-node data structure where each node may have 0 to 2 child nodes, and has one stored value, its node number in this case. A tree may either be: 11 class Result { * Complete the 'isValid' function below. • An empty tree, the root...
Write a C program to build a complete binary tree with 7 nodes using link list...
Write a C program to build a complete binary tree with 7 nodes using link list implementation. Requirements: 1) Ask the user to enter randomly seven integer numbers as data value for each node 2) Build the tree using link list 3) Print the tree in inorder , preorder , and post order 4) Use functions for each print type .
In this assignment, you will add several methods to the Binary Search Tree. You should have compl...
In this assignment, you will add several methods to the Binary Search Tree. You should have completed the following three methods in the lab: public void insert(Key key, Value value) public Value get(Key key) public void inorder(Node root) For this assignment, you will implement the following: public void remove(Node root, Key key) public Key getMin(Node n) public Key getMax(Node n) public int height(Node n) The main method contains the statements to check whether your implementation works. You need to change...
You will be given several strings full of different keyboard characters, some of which are letters...
You will be given several strings full of different keyboard
characters, some of which are letters of the alphabet.
Write a java program that creates a binary tree that uses
only the alphabetical characters (a-z, A-Z) as the value within the
leaf nodes using recursion and preorder traversal. All
other values within the tree (either the root node or internal
nodes) will be null. You may create any methods you see fit, so
long as the final binary tree is...
using java to write,show me the output. please write some
common.
You CAN NOT use inbuild functions for Tree ADT operations.
using code below to finsih
public class Main
{
public static void main(String[] args) {
BinaryTree tree = new
BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
tree.root.left.left.left = new Node(8);
tree.root.left.left .right= new Node(9);...
Consider the AVL Tree built by inserting the following sequence of integers, one at a time: 5, 2, 8, 7,9 Then we insert 11. After we insert 11, before we perform any necessary rotations, is the tree balanced? And if not, which is the root of the lowest imbalanced subtree? (a) None, since the tree is already balanced after inserting 11. (b) The node containing 5. (c) The node containing 8. (d) The node containing 11. (e) The node containing...
please solve this question:
Write a character Max-Heap Builder program in C++. The program should display the menu below. Each item in the menu should be implemented in a function. a. Add a node. One node to be added to the max-heap. b. Delete a node. One node to be deleted from the max-heap. C. Search a node. Returns true if the node exists in the max-heap, otherwise it returns false. d. Print the tree. Prints the heap in level-order...
Using JAVA
Lab Exercises 1. Complete the class AVLTree that extends BST. It should have four methods RotateLeft, Rotate Right RotateLeftRight, and RetateRightLeft. You have to provide the methods rotate Right(), rotateLeftRight and rotateRightLeft, Provide the method delete() to delete elements in the AVL tree. 2. Create an AVL tree in which the following keys are inserted in the given order: 8, 12, 14, 18, 20, 23, 15, 13, 7, 16 Then ask the user to provide any 3 elements...
please use java application to solve methods:
5,6,10,12,13 (no need for the rest)
Problem1: Create a new Java Application that has the following methods: 6 A method that generate a binary search tree (BST) where the number of nodes and the range of the values are 1. from a file. 2. A recursive method to print the BST in preorder traversal 3. A recursive method to print the BST in post-order traversal 4. A recursive method to print the BST...
Would appreciate the answer in the Java coding language please
and thank you!
10d 10h left Java 7 1. Check the Structure Autocomplete Ready 1 > import java.io.*;... 10 ALL A binary tree uses a multi-node data structure where each node may have 0 to 2 child nodes, and has one stored value, its node number in this case. A tree may either be: 11 class Result { * Complete the 'isValid' function below. • An empty tree, the root...
You will be given several strings full of different keyboard
characters, some of which are letters of the alphabet.
Write a java program that creates a binary tree that uses
only the alphabetical characters (a-z, A-Z) as the value within the
leaf nodes using recursion and preorder traversal. All
other values within the tree (either the root node or internal
nodes) will be null. You may create any methods you see fit, so
long as the final binary tree is...
Most questions answered within 3 hours.
-
A 60-Hz, 765-kV, three-phase overhead transmission line has two
ACSR 900 kcmil 54/3 conductors per phase....
asked 5 seconds ago -
The work done by the spring's restoring force
on the free end of a spring while...
asked 1 minute ago -
Reynold company is considering an investment of $130,000 in
new equipment. The new equipment is expected...
asked 17 minutes ago -
If a company’s stock price (P0) goes up, and nothing else
changes, Ke (the required rate...
asked 4 minutes ago -
As a manager in today society, how can I use Harry Truman's
leadership skills and attributes...
asked 6 minutes ago -
The decomposition of SO2Cl2 is first order
and has a rate constant of + 2.90 x...
asked 6 minutes ago -
Why is protecting equipment an important element of this
concept, and how are some of the...
asked 16 minutes ago -
An asset used in a four-year project falls in the five-year
MACRS class (MACRS Table) for...
asked 18 minutes ago -
Break-even time. Hampton Corporation’s research
and development department is presenting a proposal for new product
research....
asked 21 minutes ago -
At Lake Itasca in Minnesota, the Mississippi river is only 25.0
feet wide. If you are...
asked 22 minutes ago -
A 2.0 μF parallel-plate air-filled capacitor is connected
across a 10 V battery.
(a) Determine the...
asked 32 minutes ago -
Write in Python This program:
1. Correct the compute_cells_state function which receives as
parameter an array...
asked 22 minutes ago