BINARY TREE OPERATIONS-INSERT,SEARCH,DELETE,DISPLAY IN JAVA.

/*
TOPIC: BINARY TREE OPERATIONS-INSERT,SEARCH,DELETE,DISPLAY.
DATE:20/9/2012
*/
import java.util.*;
import java.io.*;
class Node
{
int data;
Node left,right;
public Node(int data)
{
 this.data=data;
 left=right=null;
}
}
class BST
{
private Node root;
public BST()
{
 root=null;
}
Node father(Node p)
{
if(p==root)
return null;
Node q=root;
while(q!=null)
{
 if(q.left==p||q.right==p)
 return q;
 if(p.data<=q.data)
 q=q.left;
 else
 q=q.right;
}
return null;
}
public Node findmax(Node r)
{
if(r.right==null)
return r;
else
return (findmax(r.left));
}
public Node findmin(Node r)
{
if(r.left==null)
return r;
else
return (findmin(r.left));
}
public void insert(int ele)
{
Node p=new Node(ele);
if(root==null)
{
 root=p;
 return;
}
Node q=root;
while(q!=null)
{
 if(p.data<=q.data)
  if(q.left==null)
  {
   q.left=p;
   break;
  }
 else q=q.left;
 else if(q.right==null)
 {
  q.right=p;
  break;
 }
 else
 q=q.right;
}
}
public void inorder(Node x)
{
if(x!=null)
{
 inorder(x.left);
 System.out.println(x.data+" ");
 inorder(x.right);
}
}
public void preorder(Node x)
{
if(x!=null)
{
 System.out.println(x.data+" ");
 preorder(x.left);
 preorder(x.right);
}
}
public void postorder(Node x)
{
if(x!=null)
 {
  postorder(x.left);
  postorder(x.right);
  System.out.println(x.data+" ");
 }
}
public Node get_root()
{
 return root;
}
boolean search(int ele)
{
Node q=root;
while(q!=null)
{
 if(q.data==ele)
 {
  System.out.println("element found");
  return true;
 }
 if(ele<q.data)
  q=q.left;
 else
  q=q.right;
}
System.out.println("element not found");
return false;
}
public void delete(int ele)
{
if(root==null)
{
 System.out.println("Tree is empty");
 return;
}
Node q=root;
while(q!=null)
{
 if(q.data==ele)
 break;
 if(ele<q.data)
 q=q.left;
 else
 q=q.right;
}
if(q==null)
{
 System.out.println("element not found");
 return;
}
if(q.left==null&&q.right==null)
{
 if(q==root)
 {
  root=null;
  return;
 }
if(father(q).left==q)
 father(q).left=null;
else
 father(q).right=null;
return;
}
if(q.left!=null)
{
 Node ptr=findmax(q.left);
 int val=ptr.data;
 delete(ptr.data);
 q.data=val;
 return;
}
if(q==root)
{
 root=root.right;
 return;
}
if(father(q).left==q)
 father(q).left=q.right;
else
 father(q).right=q.right;

}
}
class Demo
{
public static void main(String args[])
{
PrintStream p=System.out;
 int ele;
 Scanner src=new Scanner(System.in);
 p.println("Enter no of nodes to be created initially");
 int n=src.nextInt();
 BST obj=new BST();
 for(int i=0;i<n;i++)
 {
  p.println("enter data");
  ele=src.nextInt();
  obj.insert(ele);
 }
while(true)
{

p.println("1: Insert ");
p.println(" 2:Inorder");
p.println("3:Preorder");
p.println("4:Postorder");
p.println("5:DELETE");
p.println("6:SEARCH");
p.println("7:EXIT");
  int ch=src.nextInt();
  if(ch==7){p.println("
THANK U CODED BY TG");
  break;}
  switch(ch)
  {
  case 1: p.println("enter element to be inserted");
          ele=src.nextInt();
          obj.insert(ele);
          break;
  case 2: if(obj.get_root()!=null)
           obj.inorder(obj.get_root());
          else
           p.println("tree is empty");
          break;
  case 3: if(obj.get_root()!=null)
           obj.preorder(obj.get_root());
          else
           p.println("tree is empty");
          break;
  case 4: if(obj.get_root()!=null)
           obj.postorder(obj.get_root());
          else
           p.println("tree is empty");
          break;  
  case 5: if(obj.get_root()!=null)
          {
           p.println("enter the element to be deleted");
           ele=src.nextInt();
           obj.delete(ele);
          }
          else
           p.println("tree is empty");
          break;
  case 6: if(obj.get_root()!=null)
          {
           p.println("enter the element to be searched");
           ele=src.nextInt();
          obj.search(ele);
          }
          else
           p.println("tree is empty");
          break;
  }
}
}
}

/*
OUTPUT:
java Demo
Enter no of nodes to be created initially
1
enter data
10
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
1
enter element to be inserted
5
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
1
enter element to be inserted
30
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
1
enter element to be inserted
25
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
1
enter element to be inserted
40
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
1
enter element to be inserted
27
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
1
enter element to be inserted
45
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
2
5
10
25
27
30
40
45
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
5
enter the element to be deleted
45
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
2
5
10
25
27
30
40
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
5
enter the element to be deleted
25
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
2
5
10
27
30
40
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
5
enter the element to be deleted
30
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
2
5
10
27
40
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
6
enter the element to be searched
27
element found
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
6
enter the element to be searched
100
element not found
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
7
THANK U CODED BY TG/*