class
BSTNode {
int
key;
BSTNode left, right;
public
BSTNode(int
item) {
key = item;
left = right =
null;
}
}
class
BST_Tree {
BSTNode root;
BST_Tree() { // Constructor
root =
null;
}
boolean
search(int
key){
return
(searchRec(root, key) !=
null);
}
public
BSTNode searchRec(BSTNode root,
int
key) {
if
(root==null
|| root.key==key)
return
root;
if
(root.key > key)
return
searchRec(root.left, key);
return
searchRec (root.right, key);
}
void
deleteKey(int
key) {
root = deleteRec(root, key);
}
/* A recursive function to insert a new key in BST */
BSTNode deleteRec(BSTNode root,
int
key) {
/* Base Case: If the tree is empty */
if
(root ==
null)
return
root;
/* Otherwise, recur down the tree */
if
(key <>
root.left = deleteRec(root.left, key);
else
if
(key > root.key)
root.right = deleteRec(root.right, key);
// if key is same as root's key, then This is the target
else
{
// node with only one child or no child
if
(root.left ==
null)
return
root.right;
else
if
(root.right ==
null)
return
root.left;
// node with two children: Get the inorder successor
// (smallest in the right subtree)
root.key = minValue(root.right);
// Delete the inorder successor
root.right = deleteRec(root.right, root.key);
}
return
root;
}
int
minValue(BSTNode root) {
int
minv = root.key;
while
(root.left !=
null) {
minv = root.left.key;
root = root.left;
}
return
minv;
}
void
insert(int
key) {
root = insertRec(root, key);
}
/* A recursive function to insert a new key in BST */
BSTNode insertRec(BSTNode root,
int
key) {
/* If the tree is empty, return a new node */
if
(root ==
null) {
root =
new
BSTNode(key);
return
root;
}
/* Otherwise, recur down the tree */
if
(key <>
root.left = insertRec(root.left, key);
else
if
(key > root.key)
root.right = insertRec(root.right, key);
return
root;
}
void
inorder() {
inorderRec(root);
}
// A utility function to do inorder traversal of BST
void
inorderRec(BSTNode root) {
if
(root !=
null) {
inorderRec(root.left);
System.
out
.print(root.key + " ");
inorderRec(root.right);
}
}
void
preorder() {
preorderRec(root);
}
void
preorderRec(BSTNode root) {
if
(root !=
null) {
System.
out
.print(root.key + " ");
preorderRec(root.left);
preorderRec(root.right);
}
}
void
postorder() {
postorderRec(root);
}
void
postorderRec(BSTNode root) {
if
(root !=
null) {
postorderRec(root.left);
postorderRec(root.right);
System.
out
.print(root.key + " ");
}
}
}
public
class
BST_Recursive {
public
static
void
main(String[] args) {
BST_Tree tree =
new
BST_Tree();
System.
out
.println("Build a tree by inserting :\n 50 30 20 40 70 60 80");
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
System.
out
.println("\nPre-order traversal of the given tree");
tree.preorder();
System.
out
.println("\nIn-order traversal of the given tree");
tree.inorder();
System.
out
.println("\nPost-order traversal of the given tree");
tree.postorder();
System.
out
.println("\n\nDelete 20");
tree.deleteKey(20);
System.
out
.println("Inorder traversal of the modified tree");
tree.inorder();
System.
out
.println("\nDelete 30");
tree.deleteKey(30);
System.
out
.println("Inorder traversal of the modified tree");
tree.inorder();
System.
out
.println("\nDelete 50");
tree.deleteKey(50);
System.
out
.println("Inorder traversal of the modified tree");
tree.inorder();
System.
out
.println("\nSearch 70");
System.
out
.println("Found ? : " + tree.search(70) );
}
}
Task 1:
Modify BST_Recursive.java to write a complete program to implement
a spare-parts database with
itemNo, price and description
. Provide options to insert, search, delete, and show all items in order of itemNo.