Binary Search Tree - Datastructure - JAVA

Program:
import java.io.*;
class Node
{
    int data;
    public Node left;
    public Node right;
    public Node(int value)
    {
        data=value;
    }
}
class tree
{
    public Node insert(int x,Node root)
    {
        Node newnode=new Node(x);
        if(root==null)
        {
            root=newnode;
        }
        else if(x<root.data)
            root.left=insert(x,root.left);
        else
            root.right=insert(x,root.right);
        return root;
    }
    public void display(Node root)
    {
        if(root!=null)
        {
            display(root.left);
            System.out.print(root.data+" ");
            display(root.right);
        }
    }
    public int search(int x ,Node p)
    {
        while(p!=null)
        {
            if(x==p.data)
                return 1;
            else if(x<p.data)
                p=p.left;
            else
                p=p.right;
        }
        return 0;
    }
    public Node delete(int x,Node root)
    {
        Node p;
        Node parent=root;
        Node inorderSucc;
        if(root==null)
        {
            System.out.println("The tree is empty.");
        }
        p=root;
        while(p!=null && p.data!=x)
        {
            parent=p;
            if(x<p.data)
                p=p.left;
            else
                p=p.right;
        }
        if(p.left!=null&& p.right!=null)
        {
            parent=p;
            inorderSucc=p.right;
            while(inorderSucc.left!=null)
            {
                parent=inorderSucc;
                inorderSucc=inorderSucc.left;
            }
            p.data=inorderSucc.data;
            p=inorderSucc;
        }
        if(p.left==null && p.right==null)
        {
            if(parent.left==p)
                parent.left=null;
            else
                parent.right=null;
        }
        if(p.left==null && p.right==null)
        {
            if(parent.right==p)
                parent.right=p.right;
            else
                parent.left=p.right;
        }
        if(p.left!=null && p.right==null)
        {
            if(parent.right==p)
                parent.right=p.left;
            else
                parent.left=p.left;
        }
        return p;
    }
}

class bstn
{
public static void main(String arg[]) throws IOException
{
        DataInputStream x=new DataInputStream(System.in);
        int arr[]=new int[20];
        tree t1=new tree();
        Node root=null;
        System.out.print("Enter the number of elements:");
        int n=Integer.parseInt(x.readLine());
        System.out.println("\nEnter elements:");
        for(int i=0;i<n;i++)
        {
            root=t1.insert(Integer.parseInt(x.readLine()),root);
       
        }
        int flag=1;
        t1.display(root);
        do{
            System.out.println("\n1.Insert \n\t2.Search an element\n\t\t3.delete an element\n\t\t\t4.Exit");
            switch(Integer.parseInt(x.readLine()))
            {
            case 1:
                System.out.println("\nEnter the element:");
                t1.insert(Integer.parseInt(x.readLine()),root);
                t1.display(root);
                break;
            case 2:
                System.out.println("\nEnter the element to search:");
                int res=t1.search(Integer.parseInt(x.readLine()),root);
                if(res==1)
                    System.out.println("FOUND");
                else
                    System.out.println("Not found");
                break;
            case 3:
                System.out.println("\nEnter number");
                t1.delete(Integer.parseInt(x.readLine()),root);
                t1.display(root);
                break;
            case 4:
                flag=0;
                break;
        }
    }while(flag==1);
}
}
 

Output:
nn@linuxmint ~ $ javac bstn.java
nn@linuxmint ~ $ javac bstn.java
Note: bstn.java uses or overrides a deprecated API.
Note: Recompile with -Xlint:deprecation for details.
nn@linuxmint ~ $ java bstn
Enter the number of elements:5

Enter elements:
5
4
3
2
1
1 2 3 4 5 
1.Insert 
    2.Search an element
        3.delete an element
            4.Exit
1

Enter the element:
6
1 2 3 4 5 6 
1.Insert 
    2.Search an element
        3.delete an element
            4.Exit
2

Enter the element to search:
4
FOUND

1.Insert 
    2.Search an element
        3.delete an element
            4.Exit
3

Enter number
3
1 2 4 5 6 
1.Insert 
    2.Search an element
        3.delete an element
            4.Exit
4
nn@linuxmint ~ $

0 comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...