Convert the elements in the Node java class to Generic data types: BinarySearchT
ID: 3920182 • Letter: C
Question
Convert the elements in the Node java class to Generic data types:
BinarySearchTree Class
package binarysearchtree;
import java.util.*;
class BinarySearchTree
{
public static void main(String args[]) {
BST bt = new BST();
int ch;
do {
System.out.println(" Binary Search Tree Traversing");
System.out.println("1. Add Element");
System.out.println("2. Remove Element");
System.out.println("3. Search Element");
System.out.println("4. In-Order");
System.out.println("5. Pre-Order");
System.out.println("6. Post-Order");
System.out.println("7. Exit");
System.out.println("Enter your choice:");
Scanner sc = new Scanner(System.in);
ch = sc.nextInt();
switch (ch) {
case 1:
bt.create();
break;
case 2:
System.out.println(" Enter node to be Deleted :");
int d = sc.nextInt();
bt.delNode(d);
break;
case 3:
System.out.println(" Enter node to be Search :");
int s = sc.nextInt();
boolean res = bt.search(s);
if (res) {
System.out.println("Element Found " + res);
} else {
System.out.println("Element NOT Found");
}
break;
case 4:
System.out.println(" In-Order Traversing ");
bt.inOrder(bt.root);
break;
case 5:
System.out.println(" Pre-Order Traversing ");
bt.preOrder(bt.root);
break;
case 6:
System.out.println(" Post-Order Traversing ");
bt.postOrder(bt.root);
break;
case 7:
System.exit(0);
break;
default:
System.out.println("Invalid entry ");
}
} while (ch != 7);
}
}
Node Class
package binarysearchtree;
import java.util.*;
interface Operations {
void addNode(int n);
void delNode(int n);
boolean search(int n);
}
class Node {
int data;
Node lchild;
Node rchild;
Node(int id) {
data = id;
lchild = null;
rchild = null;
}
}
class BST implements Operations {
Scanner sc = new Scanner(System.in);
Node root;
BST() {
root = null;
}
public void addNode(int d) {
root = insert(root, d);
}
private Node insert(Node p, int n) {
if (p == null) {
p = new Node(n);
} else if (n < (p.data)) {
p.lchild = insert(p.lchild, n);
} else {
p.rchild = insert(p.rchild, n);
}
return p;
}
public boolean search(int key) {
Node p = root;
while (p != null) {
if (key == p.data) {
return true;
} else if (key < p.data) {
p = p.lchild;
} else {
p = p.rchild;
}
}
return false;
}
private Node delete(Node r, int key) {
Node p;
Node parent = r;
Node succ;
if (r == null) {
System.out.println("Tree is empty");
return null;
}
p = r;
while (p != null && p.data != key) {
parent = p;
if (key < p.data) {
p = p.lchild;
} else {
p = p.rchild;
}
}
if (p == null) {
System.out.println(" Node " + key + " not found for deletion");
return null;
}
if (p.lchild != null && p.rchild != null) {
parent = p;
succ = p.rchild;
while (succ.lchild != null) {
parent = succ;
succ = succ.lchild;
}
p.data = succ.data;
p = succ;
}
if (p.lchild == null && p.rchild == null) {
if (parent.lchild == p) {
parent.lchild = null;
} else {
parent.rchild = null;
}
}
if (p.lchild == null && p.rchild != null) {
if (parent.lchild == p) {
parent.lchild = p.rchild;
} else {
parent.rchild = p.rchild;
}
}
if (p.lchild != null && p.rchild == null) {
if (parent.lchild == p) {
parent.lchild = p.lchild;
} else {
parent.rchild = p.lchild;
}
}
return r;
}
public void delNode(int num) {
root = delete(root, num);
}
void create() {
int item;
System.out.println("Enter item to be added:");
item = sc.nextInt();
Node temp = new Node(item);
if (root == null) {
root = temp;
} else {
Node current = root;
Node parent = null;
while (current != null) {
parent = current;
if (item < current.data) {
current = current.lchild;
} else {
current = current.rchild;
}
}
if (parent.data > item) {
parent.lchild = temp;
} else {
parent.rchild = temp;
}
}
}
void inOrder(Node localRoot) {
if (localRoot != null) {
inOrder(localRoot.lchild);
System.out.print(localRoot.data + " ");
inOrder(localRoot.rchild);
}
}
void preOrder(Node localRoot) {
if (localRoot != null) {
System.out.print(localRoot.data + " ");
preOrder(localRoot.lchild);
preOrder(localRoot.rchild);
}
}
void postOrder(Node localRoot) {
if (localRoot != null) {
postOrder(localRoot.lchild);
postOrder(localRoot.rchild);
System.out.print(localRoot.data + " ");
}
}
}
Explanation / Answer
Please find the modified code below.
CODE
=================
import java.util.Arrays;
import java.util.*;
interface Operations<E> {
void addNode(E n);
void delNode(E n);
boolean search(E n);
}
class Node<E> implements Comparable<Node<E>>{
E data;
Node<E> lchild;
Node<E> rchild;
Node(E id) {
data = id;
lchild = null;
rchild = null;
}
@Override
public int compareTo(Node<E> o) {
return this.compareTo(o);
}
}
class BST<E> implements Operations<E> {
Scanner sc = new Scanner(System.in);
Node<E> root;
BST() {
root = null;
}
public void addNode(E d) {
root = insert(root, d);
}
private Node<E> insert(Node<E> p, E n) {
Node<E> temp = new Node<>(n);
if (p == null) {
p = new Node<E>(n);
} else if (temp.compareTo(p) < 0) {
p.lchild = insert(p.lchild, n);
} else {
p.rchild = insert(p.rchild, n);
}
return p;
}
public boolean search(E key) {
Node<E> p = root;
Node<E> temp = new Node<>(key);
while (p != null) {
if (key == p.data) {
return true;
} else if (temp.compareTo(p) < 0) {
p = p.lchild;
} else {
p = p.rchild;
}
}
return false;
}
private Node<E> delete(Node<E> r, E key) {
Node<E> p;
Node<E> temp = new Node<>(key);
Node<E> parent = r;
Node<E> succ;
if (r == null) {
System.out.println("Tree is empty");
return null;
}
p = r;
while (p != null && p.data != key) {
parent = p;
if (temp.compareTo(p)< 0) {
p = p.lchild;
} else {
p = p.rchild;
}
}
if (p == null) {
System.out.println(" Node " + key + " not found for deletion");
return null;
}
if (p.lchild != null && p.rchild != null) {
parent = p;
succ = p.rchild;
while (succ.lchild != null) {
parent = succ;
succ = succ.lchild;
}
p.data = succ.data;
p = succ;
}
if (p.lchild == null && p.rchild == null) {
if (parent.lchild == p) {
parent.lchild = null;
} else {
parent.rchild = null;
}
}
if (p.lchild == null && p.rchild != null) {
if (parent.lchild == p) {
parent.lchild = p.rchild;
} else {
parent.rchild = p.rchild;
}
}
if (p.lchild != null && p.rchild == null) {
if (parent.lchild == p) {
parent.lchild = p.lchild;
} else {
parent.rchild = p.lchild;
}
}
return r;
}
public void delNode(E num) {
root = delete(root, num);
}
void create() {
int item;
System.out.println("Enter item to be added:");
item = sc.nextInt();
Node<E> temp = new Node<>(item);
if (root == null) {
root = temp;
} else {
Node<E> current = root;
Node<E> parent = null;
while (current != null) {
parent = current;
if (item,compareTo(current) < 0) {
current = current.lchild;
} else {
current = current.rchild;
}
}
if (item,compareTo(parent) < 0) {
parent.lchild = temp;
} else {
parent.rchild = temp;
}
}
}
void inOrder(Node<E> localRoot) {
if (localRoot != null) {
inOrder(localRoot.lchild);
System.out.print(localRoot.data + " ");
inOrder(localRoot.rchild);
}
}
void preOrder(Node<E> localRoot) {
if (localRoot != null) {
System.out.print(localRoot.data + " ");
preOrder(localRoot.lchild);
preOrder(localRoot.rchild);
}
}
void postOrder(Node<E> localRoot) {
if (localRoot != null) {
postOrder(localRoot.lchild);
postOrder(localRoot.rchild);
System.out.print(localRoot.data + " ");
}
}
}
public class tester
{
public static void addAtIndex (int[] a, int x, int index) {
if(index >= a.length) {
throw new ArrayIndexOutOfBoundsException("Index out of range!!!");
}
if(a[index] == 0) {
a[index] = x;
return;
}
boolean isFull = true;
for(int i=0; i<a.length; i++) {
if(a[i] == 0) {
isFull = false;
break;
}
}
if(isFull) {
throw new ArrayIndexOutOfBoundsException("Array already full. Last element in thar array is " + a[a.length-1]);
}
for(int i = (a.length-1); i > (index-1); i--) {
a[i] = a[i-1];
}
a[index-1] = x;
}
public static void main(String[] args) {
int a[] = new int[5];
try {
addAtIndex(a, 15, 3);
addAtIndex(a, 85, 0);
addAtIndex(a, 34, 1);
addAtIndex(a, 12, 2);
addAtIndex(a, 19, 4);
//addAtIndex(a, 63, 3);
//addAtIndex(a, 12, 99);
} catch (ArrayIndexOutOfBoundsException e) {
e.printStackTrace();
}
System.out.println(Arrays.toString(a));
}
}