Breadth First Search (BFS) - Datastructure - JAVA

Program:
import java.io.*;
class quelist
{
  public int front;
  public int rear;
  public int maxsize;
  public int[] que;
 
  public quelist(int size)
  {
    maxsize = size;
    que = new int[size];
    front = rear = -1;
  }
  
  public void display()
  {
     for(int i = front;i<=rear;i++)
         System.out.print(que[i]+"    ");
  }
 
  public void enque(int x)
  {
     if(front==-1)
     front = 0;
     que[++rear]=x;
  }

  public int deque()
  {
    int temp = que[front];
    front = front +1;
    return temp;
  }

  public boolean isempty()
  {
    return((front>rear)||(front==-1));
  }
}    

class vertex
{
 public char label;
 public boolean wasvisited;
 
 public vertex(char lab)
 {
   label = lab;
   wasvisited = false;
 }
}

class graph
{
  public final int MAX = 20;
  public int nverts;
  public int adj[][];
  public vertex vlist[];
  quelist qu; 

  public graph()
  {
   nverts = 0;
   vlist = new vertex[MAX];
   adj = new int[MAX][MAX];
   qu = new quelist(MAX);
   for(int i=0;i<MAX;i++)
    for(int j=0;j<MAX;j++)
     adj[i][j] = 0;
  }

  public void addver(char lab)
  {
    vlist[nverts++] = new vertex(lab);
  }

  public void addedge(int start,int end)
  {
    adj[start][end] = 1;
    adj[end][start] = 1;
  }
  
  public int getadjunvis(int i)
  {
    for(int j=0;j<nverts;j++)
      if((adj[i][j]==1)&&(vlist[j].wasvisited==false))
      return j;
    return (MAX+1);    
  }

  public void display(int i)
  {
    System.out.print(vlist[i].label);
  }

  public int getind(char l)
  {
    for(int i=0;i<nverts;i++) 
      if(vlist[i].label==l)
      return i;
    return (MAX+1);
  }

  public void brfs()
  {
    vlist[0].wasvisited = true;
    display(0);
    qu.enque(0);
    int v2;
    while(!(qu.isempty()))
    { 
     int v1 = qu.deque();
     while((v2=getadjunvis(v1))!=(MAX+1))
      { 
    vlist[v2].wasvisited = true;
        display(v2);
        qu.enque(v2);
      }    
    }
    System.out.print("\n");
  }
}

class bfs
{
  public static void main(String args[])throws IOException
  {
    graph gr = new graph();
    InputStreamReader isr = new InputStreamReader(System.in);
    BufferedReader br = new BufferedReader(isr);
    System.out.println("Enter the number of vertices");
    int n = Integer.parseInt(br.readLine());
    System.out.println("Enter the labels for the vertices");
    for(int i=0;i<n;i++)
    {
      String temp = br.readLine();
      char ch = temp.charAt(0);
      gr.addver(ch);
    }
    System.out.println("Enter the number of edges");
    int edg = Integer.parseInt(br.readLine());
    System.out.println("Enter the vertices which you need to connect");
    for(int j=0;j<edg;j++)
    {
      System.out.println("Enter the first vertex");
      String t = br.readLine();
      char c = t.charAt(0);
      int start = gr.getind(c);
    
      System.out.println("Enter the second vertex");
      t = br.readLine();
      c = t.charAt(0);
      int end = gr.getind(c);
    
      gr.addedge(start,end);
    }
    System.out.print("The vertices in the graph traversed breadthwise:");
    gr.brfs();
  }  
}  

Output:

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 ~ $

Hashing - Chaining - Datastrucutre - JAVA

Program:
import java.io.*;
class Node
{
    int data;
    Node next;
    public Node(int x)
    {
        data=x;
        next=null;
    }
    public void display()
    {
        System.out.print(" "+data);
    }
}
class list
{
    Node first;
    public list()
    {
        first=null;
    }
    public void deletekey(int key)
    {
        Node current=first;
        Node prev=null;
        while(current.data!=key)
        {
            if(current.next==null)
            {
                System.out.println("\nNot found...");   
                return;
            }
            else
            {
                prev=current;
                current=current.next;
            }
        }
            if(current==first)
                first=first.next;
            else
            prev.next=current.next;
    }
    public void insertlast(int x)
    {
        Node newnode=new Node(x);
        if(first==null)
        {
            first=newnode;
        }
        else
        {
            Node current=first;
            while(current.next!=null)
                current=current.next;
            current.next=newnode;
        }
    }
    public boolean search(int key)
    {
        Node current=first;
        Node prev=null;
        while(current.data!=key)
        {
            if(current.next==null)
                return false;
            else
                current=current.next;
        }
            return true;
    }
    public void display()
    {
        System.out.println("\n\n");
        Node current=first;
        while(current!=null)
        {
            current.display();
            current=current.next;
        }
    }
}
class hashtable
{
    int tablesize;
    list[] H;
    public hashtable(int size)
    {
        tablesize=size;
        H= new list[tablesize];
        for(int i=0;i<tablesize;i++)
            H[i]=new list();
    }
    public int hashfunc(int key)
    {
        return key%tablesize;
    }
    public void insert(int key)
    {
        int hashval=hashfunc(key);
        H[hashval].insertlast(key);
    }
    public void delete(int key)
    {
        int hashval=hashfunc(key);
        H[hashval].deletekey(key);
    }
    public void display()
    {
        for(int i=0;i<tablesize;i++)
        {
            H[i].display();
            System.out.print("\n");
        }
    }
    public boolean search(int key)
    {
        int hashval=hashfunc(key);

        if(H[hashval].search(key))
            return true;
        else
            return false;
    }
}
class chain
{
public static void main(String arg[])throws IOException
{
    DataInputStream x= new DataInputStream(System.in);
    System.out.println("Enter tablesize:");
    int size=Integer.parseInt(x.readLine());
    hashtable t=new hashtable(size);
    System.out.println("Enter number of terms to insert:");
    int num= Integer.parseInt(x.readLine());
    System.out.println("Enter elements:");
    for(int i=0;i<num;i++)
        t.insert(Integer.parseInt(x.readLine()));
    t.display();
    System.out.println("\nEnter number to delete:");
    t.delete(Integer.parseInt(x.readLine()));
    t.display();
    System.out.println("\nEnter number to search:");
    if(t.search(Integer.parseInt(x.readLine())))
        System.out.println("Present..");
    else
        System.out.println("Not present...");
}
}

Output:
nn@linuxmint ~ $ javac chain.java
Note: chain.java uses or overrides a deprecated API.
Note: Recompile with -Xlint:deprecation for details.
nn@linuxmint ~ $ java chain
Enter tablesize:
10
Enter number of terms to insert:
12
Enter elements:
1
5
8
7
4
2
9
15
33
47
66
14







 1



 2



 33



 4 14



 5 15



 66



 7 47



 8



 9

Enter number to delete:
15







 1



 2



 33



 4 14



 5



 66



 7 47



 8



 9

Enter number to search:
5
Present..
nn@linuxmint ~ $