Using the given two Java files below, M odify the Binary Search Tree to work wit
ID: 3697964 • Letter: U
Question
Using the given two Java files below, Modify the Binary Search Tree to work with generic data instead of just integers. Create 3-4 binary search trees in your main method with different kinds of data. Upload your UML diagram representing your class and your implementation (code). UML diagram worth 20 points of the program.
BST.java
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
*/
public class BST {
public static BSTNode root;
public BST(){
this.root = null;
}
public boolean find(int id){
BSTNode current = root;
while(current!=null){
if(current.data==id){
return true;
}else if(current.data>id){
current = current.left;
}else{
current = current.right;
}
}
return false;
}
public boolean delete(int id){
BSTNode parent = root;
BSTNode current = root;
boolean isLeftChild = false;
//Case 1: The node isn't in the tree.
while(current.data!=id){
parent = current;
if(current.data>id){
isLeftChild = true;
current = current.left;
}else{
isLeftChild = false;
current = current.right;
}
if(current ==null){
return false;
}
}
//if i am here that means we have found the node
//Case 2: if node to be deleted has no children
if(current.left==null && current.right==null){
if(current==root){
root = null;
}
if(isLeftChild ==true){
parent.left = null;
}else{
parent.right = null;
}
}
//Case 3: if node to be deleted has only one child
else if(current.right==null){
if(current==root){
root = current.left;
}else if(isLeftChild){
parent.left = current.left;
}else{
parent.right = current.left;
}
}
else if(current.left==null){
if(current==root){
root = current.right;
}else if(isLeftChild){
parent.left = current.right;
}else{
parent.right = current.right;
}
}
//Case 4: The node has 2 children
else if(current.left!=null && current.right!=null){
//now we have found the minimum element in the right sub tree
BSTNode successor = getSuccessor(current);
if(current==root){
root = successor;
}else if(isLeftChild){
parent.left = successor;
}else{
parent.right = successor;
}
successor.left = current.left;
}
return true;
}
public BSTNode getSuccessor(BSTNode deleteNode){
BSTNode successsor =null;
BSTNode successsorParent =null;
BSTNode current = deleteNode.right;
while(current!=null){
successsorParent = successsor;
successsor = current;
current = current.left;
}
//check if successor has the right child, it cannot have left child for sure
// if it does have the right child, add it to the left of successorParent.
//successsorParent
if(successsor!=deleteNode.right){
successsorParent.left = successsor.right;
successsor.right = deleteNode.right;
}
return successsor;
}
public void insert(int id){
BSTNode newBSTNode = new BSTNode(id);
if(root==null){
root = newBSTNode;
return;
}
BSTNode current = root;
BSTNode parent = null;
while(true){
parent = current;
if(id<current.data){
current = current.left;
if(current==null){
parent.left = newBSTNode;
return;
}
}else{
current = current.right;
if(current==null){
parent.right = newBSTNode;
return;
}
}
}
}
public void inOrderdisplay(BSTNode root){
if(root!=null){
inOrderdisplay(root.left);
System.out.print(" " + root.data);
inOrderdisplay(root.right);
}
}
public void preOrderdisplay(BSTNode root)
{
if(root != null){
System.out.print(" " + root.data);
preOrderdisplay(root.left);
preOrderdisplay(root.right);
}
}
public void postOrderdisplay(BSTNode root)
{
if(root != null)
{
preOrderdisplay(root.left);
preOrderdisplay(root.right);
System.out.print(" " + root.data);
}
}
public static void main(String arg[]){
BST b = new BST();
b.insert(3);b.insert(8);
b.insert(1);b.insert(4);b.insert(6);b.insert(2);
b.insert(10);b.insert(9);
b.insert(20);b.insert(25);b.insert(15);b.insert(16);
System.out.println("Original Tree : ");
b.inOrderdisplay(b.root);
System.out.println("");
System.out.println("Check whether Node with value 4 exists : "
+ b.find(4));
System.out.println("Delete Node with no children (2) : "
+ b.delete(2));
b.inOrderdisplay(root);
System.out.println(" Delete Node with one child (4) : "
+ b.delete(4));
b.inOrderdisplay(root);
System.out.println(" Delete Node with Two children (10) : "
+ b.delete(10));
b.inOrderdisplay(root);
}
}
BSTNode.java
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
*/
public class BSTNode {
int data;
BSTNode left;
BSTNode right;
public BSTNode(int d)
{
this.data = d;
left = null;
right = null;
}
public void setData(int d)
{
this.data = d;
}
public int getData()
{
return data;
}
}
Explanation / Answer
# include <stdio.h>
# include <conio.h>
# include <stdlib.h>
typedef struct BST {
int data;
struct BST *lchild, *rchild;
} node;
void insert(node *, node *);
void inorder(node *);
void preorder(node *);
void postorder(node *);
node *search(node *, int, node **);
void main() {
int choice;
char ans = 'N';
int key;
node *new_node, *root, *tmp, *parent;
node *get_node();
root = NULL;
clrscr();
printf(" Program For Binary Search Tree ");
do {
printf(" 1.Create");
printf(" 2.Search");
printf(" 3.Recursive Traversals");
printf(" 4.Exit");
printf(" Enter your choice :");
scanf("%d", &choice);
switch (choice) {
case 1:
do {
new_node = get_node();
printf(" Enter The Element ");
scanf("%d", &new_node->data);
if (root == NULL) /* Tree is not Created */
root = new_node;
else
insert(root, new_node);
printf(" Want To enter More Elements?(y/n)");
ans = getch();
} while (ans == 'y');
break;
case 2:
printf(" Enter Element to be searched :");
scanf("%d", &key);
tmp = search(root, key, &parent);
printf(" Parent of node %d is %d", tmp->data, parent->data);
break;
case 3:
if (root == NULL)
printf("Tree Is Not Created");
else {
printf(" The Inorder display : ");
inorder(root);
printf(" The Preorder display : ");
preorder(root);
printf(" The Postorder display : ");
postorder(root);
}
break;
}
} while (choice != 4);
}
/*
Get new Node
*/
node *get_node() {
node *temp;
temp = (node *) malloc(sizeof(node));
temp->lchild = NULL;
temp->rchild = NULL;
return temp;
}
/*
This function is for creating a binary search tree
*/
void insert(node *root, node *new_node) {
if (new_node->data < root->data) {
if (root->lchild == NULL)
root->lchild = new_node;
else
insert(root->lchild, new_node);
}
if (new_node->data > root->data) {
if (root->rchild == NULL)
root->rchild = new_node;
else
insert(root->rchild, new_node);
}
}
/*
This function is for searching the node from
binary Search Tree
*/
node *search(node *root, int key, node **parent) {
node *temp;
temp = root;
while (temp != NULL) {
if (temp->data == key) {
printf(" The %d Element is Present", temp->data);
return temp;
}
*parent = temp;
if (temp->data > key)
temp = temp->lchild;
else
temp = temp->rchild;
}
return NULL;
}
/*
This function displays the tree in inorder fashion
*/
void inorder(node *temp) {
if (temp != NULL) {
inorder(temp->lchild);
printf("%d", temp->data);
inorder(temp->rchild);
}
}
/*
This function displays the tree in preorder fashion
*/
void preorder(node *temp) {
if (temp != NULL) {
printf("%d", temp->data);
preorder(temp->lchild);
preorder(temp->rchild);
}
}
/*
This function displays the tree in postorder fashion
*/
void postorder(node *temp) {
if (temp != NULL) {
postorder(temp->lchild);
postorder(temp->rchild);
printf("%d", temp->data);
}
}
# include <stdio.h>
# include <conio.h>
# include <stdlib.h>
typedef struct BST {
int data;
struct BST *lchild, *rchild;
} node;
void insert(node *, node *);
void inorder(node *);
void preorder(node *);
void postorder(node *);
node *search(node *, int, node **);
void main() {
int choice;
char ans = 'N';
int key;
node *new_node, *root, *tmp, *parent;
node *get_node();
root = NULL;
clrscr();
printf(" Program For Binary Search Tree ");
do {
printf(" 1.Create");
printf(" 2.Search");
printf(" 3.Recursive Traversals");
printf(" 4.Exit");
printf(" Enter your choice :");
scanf("%d", &choice);
switch (choice) {
case 1:
do {
new_node = get_node();
printf(" Enter The Element ");
scanf("%d", &new_node->data);
if (root == NULL) /* Tree is not Created */
root = new_node;
else
insert(root, new_node);
printf(" Want To enter More Elements?(y/n)");
ans = getch();
} while (ans == 'y');
break;
case 2:
printf(" Enter Element to be searched :");
scanf("%d", &key);
tmp = search(root, key, &parent);
printf(" Parent of node %d is %d", tmp->data, parent->data);
break;
case 3:
if (root == NULL)
printf("Tree Is Not Created");
else {
printf(" The Inorder display : ");
inorder(root);
printf(" The Preorder display : ");
preorder(root);
printf(" The Postorder display : ");
postorder(root);
}
break;
}
} while (choice != 4);
}
/*
Get new Node
*/
node *get_node() {
node *temp;
temp = (node *) malloc(sizeof(node));
temp->lchild = NULL;
temp->rchild = NULL;
return temp;
}
/*
This function is for creating a binary search tree
*/
void insert(node *root, node *new_node) {
if (new_node->data < root->data) {
if (root->lchild == NULL)
root->lchild = new_node;
else
insert(root->lchild, new_node);
}
if (new_node->data > root->data) {
if (root->rchild == NULL)
root->rchild = new_node;
else
insert(root->rchild, new_node);
}
}
/*
This function is for searching the node from
binary Search Tree
*/
node *search(node *root, int key, node **parent) {
node *temp;
temp = root;
while (temp != NULL) {
if (temp->data == key) {
printf(" The %d Element is Present", temp->data);
return temp;
}
*parent = temp;
if (temp->data > key)
temp = temp->lchild;
else
temp = temp->rchild;
}
return NULL;
}
/*
This function displays the tree in inorder fashion
*/
void inorder(node *temp) {
if (temp != NULL) {
inorder(temp->lchild);
printf("%d", temp->data);
inorder(temp->rchild);
}
}
/*
This function displays the tree in preorder fashion
*/
void preorder(node *temp) {
if (temp != NULL) {
printf("%d", temp->data);
preorder(temp->lchild);
preorder(temp->rchild);
}
}
/*
This function displays the tree in postorder fashion
*/
void postorder(node *temp) {
if (temp != NULL) {
postorder(temp->lchild);
postorder(temp->rchild);
printf("%d", temp->data);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.