Friday, April 27, 2012

14. BINARY TREE TRAVERSAL (RECURSIVE & NON-RECURSIVE) IN JAVA



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)
    {

        if(Start!=null)
        {
            if(Start.info==val) System.out.println("Element Found");
            Search(val,Start.left);
            Search(val,Start.right);
        }
    }
    void printPaths(Node Start)
    {
        int[] path = new int[10];
        Paths(Start, path, 0);
    }
    void Paths(Node Start, int[] path, int pathLen)
    {
        if (Start==null) return;
        path[pathLen] = Start.info;
        pathLen++;
        if (Start.left==null && Start.right==null)
            printArray(path, pathLen);
        else
        {
            Paths(Start.left, path, pathLen);
            Paths(Start.right, path, pathLen);
        }
    }
    void printArray(int[] path, int len)
    {
        int i;
        for (i=0; i<len; i++)
            System.out.print(path[i] + " ");
        System.out.println();
    }
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        Node p,q;
        int i=0,val;
        Node Start=new Node();
        BinaryTree BT=new BinaryTree();
        Insertion:
        {
        while(true)
        {
            System.out.print("Enter Node Value :");
            val=in.nextInt();
            if(val==0) break Insertion;            
            if(i++==0)
            {
                Start = BT.Insert(val);
                continue;
            }
            p=q=Start;           
            while(q!=null&&val!=p.info)
            {
                p=q;
                if(val<p.info)
                    q=p.left;
                else
                    q=p.right;
            }
            if(val==p.info)
            {
                System.out.println("Duplicate Number");
                continue;
            }
            else if(val<p.info)
                BT.setLeft(p,val);
            else
                BT.setRight(p,val);
        }
        }
        System.out.println("++++++++++++++++++++++++++++++");
        System.out.println("InOrder - Non Reursive");
        BT.InOrder(Start);
        System.out.println("\nInOrder - Reursive");
        BT.InRecur(Start);
        System.out.println("\nPreOrder - Non Reursive");
        BT.PreOrder(Start);
        System.out.println("\nPreOrder - Reursive");
        BT.PreRecur(Start);
        System.out.println("\nPostOrder - Reursive");
        BT.PostRecur(Start);
        System.out.println("\nPrint Leaves");
        BT.PrintLeaves(Start);
        System.out.println(" ");
        BT.printPaths(Start);
        System.out.print("Enter a Number = ");
        val=in.nextInt();
        BT.Search(val,Start);
        System.out.print("Enter number to Delete = ");
        val=in.nextInt();
        BT.Delete(val,Start);
        System.out.println("*****");
        BT.printPaths(Start);
    }
}