Saturday, April 16, 2011

Binary Tree Array


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");
    }
}