BINARY SEARCH TREE WITH JAVA
public class binarysearchtree {
static class Node {
int data;
Node left;
Node right;
Node(int data) {
this.data = data;
}
}
public static Node insert(Node root, int value) {
if (root == null) {
root = new Node(value);
return root;
}
if (root.data > value) {
//left sub tree
root.left = insert(root.left, value);
} else {
root.right = insert(root.right, value);
}
return root;
}
public static void inorder(Node root) {
if (root == null) {
return;
}
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
public static boolean search(Node root,int key){
if (root==null){
return false;
}
if (root.data > key){
return search(root.left,key);
} else if (root.data == key) {
return true;
} else {
return search(root.right,key);
}
}
public static Node delete(Node root,int value){
if (root.data>value){
root .left= delete(root.left,value);
} else if (root.data <value) {
root.right=delete(root.right,value);
}
else {root.data == value
case 1
if (root.left==null && root.right==null){
return null;
}
case2
if (root.left==null){
return root.right;
} else if (root.right==null) {
return root.left;
}
Node IS=inordersuccesor(root.right);
root.data=IS.data;
root.right=delete(root.right, IS.data);
}
return root;
}
public static Node inordersuccesor(Node root){
while (root.left != null){
root=root.left;
}
return root;
}
public static void printRange(Node root,int x, int y){
if(root == null){
return;
}
if (root.data >= x && root.data <= y){
printRange(root.left,x,y);
System.out.print(root.data+ " ");
printRange(root.right,x,y);
} else if (root.data>=y) {
printRange(root.left,x,y);
}
else
printRange(root.right,x,y);
}
public static void main(String[] args) {
int value[] = new int[]{8,5,3,1,4,6,10,11,14};
Node root = null;
for (int i = 0; i < value.length; i++) {
root = insert(root, value[i]);
}
inorder(root);
System.out.println();
printRange(root,3,14);
if (search(root,7)){
System.out.println("found");
}else {
System.out.println("not found");
}
delete(root,16);
inorder(root);
}
}
Comments
Post a Comment