f (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.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 ro
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.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.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
Trending now
This is a popular solution!
Step by step
Solved in 5 steps with 3 images
