Tuesday, June 12, 2012

Binary Search Tree without recursion in java




/**
 *
 * @author Naveen Kumar
 */
public class BST {
    static node1 n, root;
    public static void main(String args[])
    {
        if(n==null)
            System.out.println("node is null");
        int[] elements = {1,1,2,3,2,2,5,4,4,6,5,6,7,8,7,9};


        for(int i=0;i<elements.length;i++)
        {
            insert(elements[i], root);
            display(root);
            System.out.println();
        }
    }


    static void insert(int a, node1 n)
    {
        if(root == null)
        {
            root = new node1();
            root.data = a;
            root.count++;
            root.left = null;
            root.right = null;
        }
        else
        {
            node1 m = new node1();
            m = root;
            while(m!=null)
            {
                if(m.data>a)
                {
                    if(m.left==null)
                    {
                        node1 temp = new node1();
                        temp.data = a;
                        temp.count++;
                        temp.left = null;
                        temp.right = null;
                        m.left = temp;
                        return;
                    }
                    else
                    {
                        m = m.left;
                    }
                }
                else if(m.data<a)
                {
                    if(m.right==null)
                    {
                        node1 temp = new node1();
                        temp.data = a;
                        temp.count++;
                        temp.left = null;
                        temp.right = null;
                        m.right = temp;
                        return;
                    }
                    else
                    {
                        m = m.right;
                    }
                }
                else
                {
                    m.count++;
                    return;
                }
            }
        }
    }


    static void display(node1 n)
    {
        if(n==null)
            return;
        display(n.left);
        System.out.print(n.data+"\t");
        display(n.right);
    }
}


class node1
{
    int data;
    int count;
    node1 left;
    node1 right;


    public node1()
    {
        this.left = null;
        this.right = null;
        this.data = 0;
        this.count = 0;
    }
}

No comments:

Post a Comment