Use the following Binary Search Tree binary code to implement the following. a p
ID: 3917273 • Letter: U
Question
Use the following Binary Search Tree binary code to implement the following.
a preorder traversal, post traversal, inorder traversal, delete nodes, search for an item in the tree, count the # of nodes, insert an item into the list, check if tree is empty.
Attach the source code and the output with all the test conditions
package treessummer;
import javax.swing.JOptionPane;
class BSTNode {
int data;
BSTNode left, right;
public BSTNode() {
left = null;
right = null;
data = 0;
}
public BSTNode(int n){
left = null;
right = null;
data = n;
}
public void setLeft( BSTNode n){
left = n;
}
public void setRight( BSTNode n){
right = n;
}
public BSTNode getLeft(){
return left;
}
public BSTNode getRight(){
return right;
}
public void setData( int d){
data = d;
}
public int getData(){
return data;
}
}
class BST {
private BSTNode root;
public String output = "";
public BST(){
root = null;
}
public boolean isEmpty(){
return root == null;
}
public void insert( int data ){
root = insert( root, data);
}
public BSTNode insert( BSTNode node, int data){
if ( node == null ){
node = new BSTNode( data);
}else {
if ( data <= node.getData()){
node.left = insert(node.left, data);
}else {
node.right = insert( node.right, data);
}
}
return node;
}
public int countNodes(){
return countNodes( root );
}
private int countNodes(BSTNode r){
if ( r == null){
return 0;
}else {
int k = 1;
k += countNodes( r.getLeft());
k += countNodes( r.getRight());
return k;
}
}
public void preOrder(){
preOrder( root );
}
public void preOrder( BSTNode r ){
if ( r != null ){
output += " " + " " + r.getData();
preOrder( r.getLeft());
preOrder( r.getRight());
}
}
public void postOrder() {
postOrder( root );
}
public void postOrder( BSTNode r ){
if ( r != null ){
preOrder( r.getLeft());
preOrder( r.getRight());
output += " " + " " + r.getData();
}
}
public boolean search( int val ){
return search( root, val );
}
public boolean search( BSTNode r, int val){
boolean found = false;
while ( ( r != null ) && (!found)){
int rval = r.getData();
if ( val < rval ){
r = r.getLeft();
}else if ( val > rval ){
r = r.getRight();
}else {
found = true;
break;
}
found = search ( r, val);
}
return found;
}
}
public class TreesSummer {
public static String output = "";
public static void main(String[] args) {
BST bst = new BST();
while ( true ){
int choice =Integer.parseInt(JOptionPane.showInputDialog(" Binary Search Tree Operations"
+ " Make a selection from the following choices "
+ " 1. Insert an Item "
+ " 2. Delete an Item "
+ " 3. Search for an item "
+ " 4 Count Nodes "
+ " 5 Check if isEmpty "
+ " 6 print the Tree in PostOrder "
+ " 7 print the Tree in PreOrder "
+ " 8 Exit program "));
output = "";
switch ( choice ){
case 1:
int num =
Integer.parseInt(JOptionPane.showInputDialog(" Enter integer element to insert"));
bst.insert ( num );
break;
case 2:
num =
Integer.parseInt(JOptionPane.showInputDialog(" Enter integer element to delete"));
//bst.delete ( num );
break;
case 3:
num =
Integer.parseInt(JOptionPane.showInputDialog(" Enter integer element to Search"));
output += " Search Result : " + bst.search ( num );
break;
case 4:
output += " Number of Nodes in the Tree : " + bst.countNodes();
break;
case 5:
output += " The Status of the Tree : " + bst.isEmpty();
break;
case 6:
output += " The Tree in Post Order, i.e. Postfix " ;
bst.postOrder();
case 7:
output += " The Tree in Pre Order, i.e. Prefix " ;
bst.preOrder();
case 8:
output += " The End of program ..Exit";
break;
}
JOptionPane.showMessageDialog(null, output);
}
}
}
Explanation / Answer
// You are missing inorder traversal. Therefore I am only adding the functions for it to make the answer
//less complicated. I hope i got what u actually required for.
public void inOrder(){
postOrder(root);
}
public void inOrder(BSTNode r){
if(r==null){
return;
}
inOrder(r.left);
output += " " + " " + r.getData();
inOrder(r.right);
}
//All the best
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.