Home Archives for April 2011

Friday, April 15, 2011

Binary Tree Array

    No comments

import java.util.Scanner;

class NodeBT
{
    int info;
    boolean used;
}

public class BinaryTreeArray
{

    NodeBT node[]=new NodeBT[20];

    void MakeTree(int val)
    {
        node[0]=new NodeBT();
        node[0].info=val;
        node[0].used=true;
        for(int i=1;i<20;i++)
        {
            node[i]=new NodeBT();
            node[i].info=0;
            node[i].used=false;
        }
    }

    void setLeft(int p,int val)
    {
        int l=2*p+1;
        if(l>=20)
            System.out.println("Array Overflow");
        else if(node[l].used==true)
            System.out.println("\nInvalid insertion");
        else
        {
            node[l].info=val;
            node[l].used=true;
        }
    }

    void setRight(int p,int val)
    {
        int r=2*p+2;
        if(r>=20)
            System.out.println("Array overflow");
        else if(node[r].used==true)
            System.out.println("\nInvalid insertion");
        else
        {
        node[r].info=val;
        node[r].used=true;
        }
    }

    public static void main(String[] args)
    {
        BinaryTreeArray BTA=new BinaryTreeArray();
        Scanner in = new Scanner(System.in);
        int i=0,p,q,val;
        Insertion:
        {
        while(true)
        {
            System.out.println("Enter numbers");
            val=in.nextInt();
            if(i++==0)
            {
                BTA.MakeTree(val);
                continue;
            }
            if(val==0) break Insertion;
            p=q=0;
            while(q < 20 && BTA.node[q].used==true && val!=BTA.node[p].info)
            {
                p=q;
                if(val<BTA.node[p].info)
                q=2*p+1;
                else
                q=2*p+2;
            }
            if(val==BTA.node[p].info)
                System.out.println("Duplicate Value");
            else if (val<BTA.node[p].info)
                BTA.setLeft(p,val);
            else
                BTA.setRight(p,val);
        }
        }
        for(i=0;i<20;i++)
            System.out.print(BTA.node[i].info + " -> ");
        System.out.println(" End");
    }
}

Binary Tree with Traversels– InOrder, PreOrder, PostOrder – (Recursive& Non-Recursive)

    No comments

import java.util.Scanner;
import java.util.Stack;

public class Node
{
    int info;
    Node next,prev;
    Node left,right;
}

public class BinaryTree
{
    Node Insert(int val)
    {
        Node t=new Node();
        t.info=val;
        return(t);
    }
    void setLeft(Node p,int val)
    {
        if(p==null || p.left!=null)
            System.out.println("\nInvalid Insertion");
        else
            p.left=Insert(val);
    }
    void setRight(Node p,int val)
    {
        if(p==null || p.right!=null)
            System.out.println("\nInvalid insertion");
        else
            p.right=Insert(val);
    }
    void InRecur(Node Start)
    {

        if(Start!=null)
        {
            InRecur(Start.left);
            System.out.print(Start.info + " ");
            InRecur(Start.right);
        }
    }
    void PreRecur(Node Start)
    {
        if(Start!=null)
        {
            System.out.print(Start.info + " ");
            PreRecur(Start.left);
            PreRecur(Start.right);
        }
    }
    void PostRecur(Node Start)
    {
        if(Start!=null)
        {
            PostRecur(Start.left);
            PostRecur(Start.right);
            System.out.print(Start.info + " ");
        }
    }
    void PrintLeaves(Node Start)
    {
        if(Start!=null)
        {
            PrintLeaves(Start.left);
            PrintLeaves(Start.right);
            if (Start.left==null&&Start.right==null)
                System.out.print(Start.info + " ");
        }
    }
    void InOrder(Node Start)
    {
        Node p;
        Stack s=new Stack();
        p=Start;
        do
        {
            while(p!=null)
            {
                s.push(p);
                p=p.left;
            }
            if(s.isEmpty()==false)
            {
                p=(Node)s.pop();
                System.out.print(p.info + " ");
                p=p.right;
            }
        }while(s.isEmpty()==false||p!=null);
    }
    void PreOrder(Node Start)
    {
        Node p;
        Stack s=new Stack();
        s.push(Start);
        while (s.isEmpty()==false)
        {
            p=(Node)s.pop();
            System.out.print(p.info + " ");
            if(p.right!=null)
                s.push(p.right);
            if (p.left!=null)
                s.push(p.left);
        }
    }
    void Delete(int val,Node Start)
    {
        Node curr;
        Node par;
        par=curr=Start;
        while(curr!=null&&val!=curr.info)
        {
            par=curr;
            if(val<par.info)
                curr=par.left;
            else
                curr=par.right;
        }
        if(curr.left==null && curr.right==null)
        {
            if(par.right==curr)
                par.right=null;
            if(par.left==curr)
                par.left=null;
        }
        if(curr.left!=null && curr.right==null)
        {
           if(curr==par.left)
               par.left=curr.left;
           if(curr==par.right)
               par.right=curr.left;
        }
        if(curr.left==null && curr.right!=null)
        {
            if(curr==par.left)
               par.left=curr.right;
           if(curr==par.right)
               par.right=curr.right;
        }
        if(curr.left!=null&&curr.right!=null)
        {
            Node t=curr.right;
            Node pt=curr.right;
            while(t.left!=null)
            {
                pt=t;
                t=t.left;
            }
            if(par.left==curr)
                par.left.info=t.info;
            else par.right.info=t.info;
            if(t.right==null)
                pt.left=null;
            else
                pt.left=t.right;
        }
    }
    void Search(int val,Node Start)
    {

Merging two Link List

    No comments

import java.util.Scanner;
import java.util.Stack;
public class MergeList
{
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        SingleLL s1=new SingleLL();
        SingleLL s2=new SingleLL();
        int i,j;
        System.out.println("Enter 5 Elements for Link 1");
        for(i=0;i<5;i++)
            s1.AddEnd(in.nextInt());
        System.out.println("Enter 5 Elements for Link 2");
        for(i=0;i<5;i++)
            s2.AddEnd(in.nextInt());
        SingleLL s3=new SingleLL();
        s3=s1;
        s3.end.next=s2.start;
        Stack s=new Stack();
        s3.curr=s3.start;
        while(s3.curr!=null)
        {
            s.push(s3.curr.info);
            s3.curr=s3.curr.next;
        }
        for(j=0;j<10;j++)
            System.out.print(s.pop() + " -> ");
    }
}


Circular Queue

    No comments

import java.util.*;
public class CircularQueue
{
    int front,rear,size=5;
    int a[]=new int[size];

    CircularQueue()
    {
        front=rear=size-1;
    }

    void Insert(int n)
    {
        Ins:
        {
        if(rear==size-1)
            rear=0;
        else rear++;
        if(rear==front)
        {
            System.out.println("Overflow");
            break Ins;
        }
        a[rear]=n;
        }
    }

    void Remove()
    {
    if(front==size-1)
        front=0;
    else ++front;
    if(front==rear)
        System.out.println("Queue Empty");
    }

    void Display()
    {
        System.out.print("Back -> ");
        int n=front+1;
        if(n==size)
            n=0;
        while(n<=rear)
        {
            System.out.print(a[n++] + " -> ");
            if(n==size)
                n=0;
        }
        System.out.println("Front");
    }

    public static void main(String[] args)
    {
        CircularQueue a=new CircularQueue();
        Scanner in=new Scanner(System.in);
        int val,ch;
        while (true)
        {
            System.out.println("Enter your Choice");
            System.out.println("\n-------------------------------------");
            System.out.println("1 : Add\t2 : Del\t3 : Display\t4 : Exit");
            ch=in.nextInt();
            switch(ch)
            {
                case 1:
                {
                    System.out.println("Enter Value To Insert");
                    val=in.nextInt();
                    a.Insert(val);
                    break;
                }
                case 2:
                {
                    a.Remove();
                    break;
                }
                case 3:
                {
                    a.Display();
                    break;
                }
                case 4: System.exit(0);
                default: continue;
            }
        }
    }
}

Double Link List with Operations - Add in Beginning, Add at End, Del at Beg, Del at End, Del any Element, Display, Search

    No comments

import java.util.Scanner;

public class Node
{
    int info;
    Node next,prev;
    Node left,right;
}

public class DoubleLL
{
    Node start=new Node();
    Node end=new Node();
    Node curr=new Node();
    int num;
   
    DoubleLL()
    {
        start=null;
        end=null;
        num=0;
    }
    void AddBeg(int val)
    {
        Node t=new Node();
        t.info=val;
        if(num++==0)
        {
            t.next=null;
            t.prev=null;
            end=t;
        }
        else
        {
            start.prev=t;
            t.next=start;
        }
        start=t;
    }
    void AddEnd(int val)
    {
        Node t=new Node();
        t.info=val;
        if(num++==0)
        {
            t.next=null;
            t.prev=null;
            start=t;
        }
        else
        {
            end.next=t;
            t.prev=end;
        }
        end=t;
    }
    void DelBeg()
    {
        if(num==0)
            System.out.println("Linked List Empty");
        else
        {
            if(start==end)
            {
                start=null;
                end=null;
                num=0;
            }
            else
            {
                start=start.next;
                start.prev=null;
            }
        }
    }
    void DelEnd()
    {
        if(num==0)
            System.out.println("Linked List Empty");
        else
        {
            if(start==end)
            {
                start=null;
                end=null;
                num=0;
            }
            else
            {
                end=end.prev;
                end.next=null;
            }
        }
    }
    void Search(int val)
    {
        Loop:
        {
        for(curr=start;curr!=null;curr=curr.next)
        {
            if(curr.info==val)
            {
                System.out.println("Element Found");
                break Loop;
            }
        }
        System.out.println("Element Not Found");
        }
    }
    void Display()
    {
        curr=start;
        System.out.print("Start -> ");
        while(curr!=null)
        {
            System.out.print(curr.info + " -> ");
            curr=curr.next;
        }
        System.out.println("End");
    }
    public static void main(String[] args)
    {
        int ch,val;
        DoubleLL dl=new DoubleLL();
        Scanner in = new Scanner(System.in);
        while(true)
        {
            System.out.println("-----------------------------------");
            System.out.println("Enter your Choice");
            System.out.println("1 : Add Beg  2 : Add End 3 : Del Beg 4 : Del End 5 : Display 6 : Search  7 : Exit");
            ch=in.nextInt();
            switch(ch)
            {

Single Link-List with Operations - Add in Beginning, Add at End, Del at Beg, Del at End, Del any Element, Display, Search

    No comments

import java.util.Scanner;
public class SingleLL
{
    Node start=new Node();
    Node end=new Node();
    Node curr=new Node();
    int num;

    SingleLL()
    {
        start=null;
        end=null;
        num=0;
    }
   
    void AddBeg(int val)
    {
        Node t=new Node();
        t.info=val;
        if(num++==0)
            end=t;
        else
            t.next=start;
        start=t;
    }

    void AddEnd(int val)
    {

        Node t=new Node();
        t.info=val;
        t.next=null;
        if(num++==0)
            start=t;
        else
            end.next=t;
        end=t;
    }

    void DelBeg()
    {
        if(num==0)
            System.out.println("Linked List is Empty");
        else
        {
            if(start==end)
            {
                start=null;
                end=null;
                num=0;
            }
            else
                start=start.next;
        }
    }

    void DelEnd()
    {
        if(num==0)
            System.out.println("Linked List is Empty");
        else
        {
            if(start==end)
            {
                start=null;
                end=null;
                num=0;
            }
            else
            {
                curr=start;
                while(curr.next!=end)
                    curr=curr.next;
                end=curr;
                end.next=null;
            }
        }
    }
   
    void DelEle(int val)
    {
        if(num==0)
            System.out.println("Linked List is Empty");
        else
        {
            curr=start;
            Node prev=new Node();
            if(end==start && start.info==val)
            {
                start=end=null;
                num=0;
            }
            else if(start.info==val)
                start=start.next;
            else if(end.info==val)
            {
                System.out.println("HEllo");
                curr=start;
                while(curr.next!=end)
                    curr=curr.next;
                end=curr;
                end.next=null;
            }
            else
            {
                curr=start;
                while(curr.info!=val)
                {
                    prev=curr;
                    curr=curr.next;
                }
                prev.next=curr.next;
            }           
        }
    }

    void Display()
    {
        curr=start;
        System.out.print("Start -> ");
        while(curr!=null)
        {
            System.out.print(curr.info + " -> ");
            curr=curr.next;
        }
        System.out.println("End");
    }

    void Search(int val)
    {
        Loop:
        {
        for(curr=start;curr!=null;curr=curr.next)
        {
            if(curr.info==val)
            {
                System.out.println("Element Found");
                break Loop;
            }
        }
        System.out.println("Element Not Found");
        }
    }

    public static void main(String args[])
    {
        int ch,val;
        SingleLL sl=new SingleLL();
        Scanner in = new Scanner(System.in);
        while(true)
        {
            System.out.println("-----------------------------------");
            System.out.println("Enter your Choice");
            System.out.println("1 : Add Beg  2 : Add End  3 : Del Beg  4 : Del End  5 : Del Ele  6 : Display  7 : Search  8 : Exit");
            ch=in.nextInt();
            switch(ch)
            {

Stack Operations – Push, Pop & Display for Characters

    No comments

import java.io.IOException;
import java.util.Scanner;
public class Stack_Char
{
    char arr[];
    int top;
   
    Stack_Char()
    {
        arr=new char[30];
        top=-1;
    }

    void Push(char val)
    {
        if(top==30)
            System.out.println("Stack OVerflow");
        else
            arr[++top]=val;
    }
   
    char Pop()
    {
        if(top==-1)
        {
            System.out.println("Stack Underflow");
            return 0;
        }

        else
        {
            return (char)arr[top--];
        }
    }

    void Display()
    {
        if(top==-1)
               System.out.println("Stack is Empty");
        else
        {
            System.out.println("Stack is");
            for(int i=0;i<=top;i++)
                System.out.print((char)arr[i] + "-");
        }
        System.out.println(" ");
    }

    boolean isEmpty()
    {
        if (top<0)
            return true;
        else
            return false;
    }

    public static void main(String[] args) throws IOException
    {
        Scanner in = new Scanner(System.in);
        int ch;
        char val;
        Stack_Num s=new Stack_Num();
        while(true)
        {
            System.out.println("Choose");
            System.out.println("1 : Push\t2 : Pop\t3 : Display\t4 : Exit");
            ch=in.nextInt();
            switch(ch)
            {
                case 1:
                {
                    System.out.println("Enter Value");
                    val=(char)System.in.read();
                    s.Push(val);
                    break;
                }
                case 2:
                {
                    System.out.println("Popped Value is " + s.Pop());
                    break;
                }
                case 3:
                {
                    s.Display();
                    break;
                }
                case 4:
                {
                    System.exit(0);
                }
                default:
                    System.out.println("Wrong Choice");
            }
        }
    }
}


Stack Operations – Push, Pop & Display for Numbers

    No comments

import java.util.Scanner;
public class Stack_Num
{
    double arr[];
    int top;
   
    void Push(double val)
    {
        if(top==9)
            System.out.println("Stack OVerflow");
        else
            arr[++top]=val;
    }
   
    double Pop()
    {
        if(top==-1)
        {
            System.out.println("Stack Underflow");
            return 0;
        }
        else
        {
            return arr[top--];
        }
    }


    void Display()
    {
        if(top==-1)
               System.out.println("Stack is Empty");
        else
        {
            System.out.println("Stack is");
            for(int i=0;i<=top;i++)
                System.out.print(arr[i] + "-");
        }
        System.out.println(" ");
    }

    boolean isEmpty()
    {
        if (top<0)
            return true;
        else
            return false;
    }

    Stack_Num()
    {
        top=-1;
        arr=new double[10];
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int ch,val;
        Stack_Num s=new Stack_Num();
        while(true)
        {
            System.out.println("Choose");
            System.out.println("1 : Push\t2 : Pop\t3 : Display\t4 : Exit");
            ch=in.nextInt();
            switch(ch)
            {
                case 1:
                {
                    System.out.println("Enter Value");
                    val=in.nextInt();
                    s.Push(val);
                    break;
                }
                case 2:
                {
                    System.out.println("Popped Value is " + s.Pop());
                    break;
                }
                case 3:
                {
                    s.Display();
                    break;
                }
                case 4:
                {
                    System.exit(0);
                }
                default:
                    System.out.println("Wrong Choice");
            }
        }
    }
}

Link List with Queue

    No comments

import java.util.Scanner;

public class Node
{
    int info;
    Node next,prev;
    Node left,right;
}

public class QueueLL
{
    Node start=new Node();
    Node end=new Node();
    Node curr=new Node();
    int ch,num;
    Object obj=new Object();

    QueueLL()
    {
        start=null;
        end=null;
        num=0;
    }

    void Add(int val)
    {

        Node t=new Node();
        t.info=val;
        if(num++==0)
            start=t;
        else
           t.next=end;
        end=t;
    }

    void Del()
    {
        if(num==0)
            System.out.println("Queue is Empty");
        else
        {
            if(start==end)
            {
                start=null;
                end=null;
                num=0;
            }
            else
            {
                curr=end;
                while(curr.next!=start)
                    curr=curr.next;
                start=curr;
                start.next=null;
            }
        }
    }

    void Display()
    {
        curr=end;
        System.out.print("Back -> ");
        while(curr!=null)
        {
            System.out.print(curr.info + " -> ");
            curr=curr.next;
        }
        System.out.println("Front");
    }

    public static void main(String args[])
    {
        int ch,val;
        QueueLL q=new QueueLL();
        Scanner in = new Scanner(System.in);
        while(true)
        {
            System.out.println("Enter your Choice");

            System.out.println("-------------------------------------");
            System.out.println("1 : Add\t2 : Del\t3 : Display\t4 : Exit");
            ch=in.nextInt();
            switch(ch)
            {
                case 1:
                {
                    System.out.print("Enter a Number = ");
                    val=in.nextInt();
                    q.Add(val);
                    break;
                }
                case 2:
                {
                    q.Del();
                    break;
                }
                case 3:
                {
                    q.Display();
                    break;
                }
                case 4:
                    System.exit(0);
                    break;
                default : continue;
            }
        }
    }
}

Subscribe to: Posts ( Atom )