import java.util.*;
class BinaryTree {
int data;
BinaryTree left, right;
BinaryTree(int x) {
this.left=this.right=null; data=x;
}
public void insert( int i ) {
if (i <= data) {
if (left != null) left.insert(i);
else left = new BinaryTree( i );
}
else if (i >= data) {
if (right != null) right.insert(i);
else right = new BinaryTree( i );
}
}
public void inOrder(BinaryTree tree) {
if(tree!=null) {
inOrder(tree.left);
System.out.print(tree.data+" ");
inOrder(tree.right); }
}
public static int min(BinaryTree node) {
if (node.left == null) {
return node.data;
}
return min(node.left);
}
public static BinaryTree deleteNodeInBST(BinaryTree node, int data) {
if (null == node) {
System.out.println("Element is not in binary search tree");
return null;
}
if (data < node.data) {
node.left = deleteNodeInBST(node.left, data);
} else if (data > node.data) {
node.right = deleteNodeInBST(node.right, data);
} else { // case for equality
// Now we see that whether we can directly delete the node
if (node.left != null && node.right != null) {
int minInRightSubTree = min(node.right);
node.data = minInRightSubTree;
node.right = deleteNodeInBST(node.right, minInRightSubTree);
} else { // either one child or leaf node
if (node.left == null && node.right == null) {
node = null;
} else {// one child case
BinaryTree deleteNode = node;
node = (node.left != null) ? (node.left) : (node.right);
deleteNode = null;
}
}
}
return node;
}
public static void main (String args[]) {
char choice='y'; int n, d;
Scanner sc = new Scanner(System.in);
System.out.print("Enter Root node value = ");
n=sc.nextInt();
System.out.print("Enter ur Choice(y/n) = ");
choice=sc.next().charAt(0); BinaryTree ob=new BinaryTree(n);
while (choice == 'y') {
System.out.print("Enter node value = ");
n=sc.nextInt(); ob.insert(n);
System.out.print("Enter ur Choice(y/n) = ");
choice=sc.next().charAt(0);
}
System.out.print("\nInorder Traversal = "); ob.inOrder(ob);
System.out.print("\nEnter the Node to delete = ");
d = sc.nextInt(); ob.deleteNodeInBST(ob, d);
System.out.print("\n After deleting the Node "+d+" = "); ob.inOrder(ob);
}
}
Output:
Inorder Traversal = 2 10 16 50 110
Enter the Node to delete = 16
After deleting the Node 16 = 2 10 50 110
 { this.left=this.right=null; data=x; } public v…){kind=link}
تعليقات
إرسال تعليق
شاركنا الآراء ،،