[Java] 이진 트리를 순회하는 알고리즘

class TreeNode {

    TreeNode Lchild;

    Object data;

    TreeNode Rchild;

}

class BirnaryTree{

    public static int count;

    public static TreeNode createBT()

    {

        return new TreeNode();

    }

    public boolean isEmpty(TreeNode p)

    {

        if(p == null) return true;

        else return false;

    }

    public void makeBT(TreeNode node, TreeNode LC, Object data, TreeNode RC)

    {

        node.Lchild = LC;

        node.data = data;

        node.Rchild = RC;

    }

    public  TreeNode LchildSubtree(TreeNode p)

    {

        if(isEmpty(p.Lchild))   return null;

        else return p.Lchild;

    }

    public TreeNode RchildSubtree(TreeNode p)

    {

        if(isEmpty(p.Rchild))   return null;

        else return p.Rchild;

    }

    public Object data(TreeNode p)

    {

        if(isEmpty(p)) return null;

        else return p.data;

    }

    public void inOrder(TreeNode p)

    {

        if(!isEmpty(p))

        {

            inOrder(p.Lchild);

            System.out.print(data(p)+" ");

            inOrder(p.Rchild);

        }

    }

    public void postOrder(TreeNode p)

    {

        if(!isEmpty(p))

        {

            postOrder(p.Lchild);

            postOrder(p.Rchild);

            System.out.print(data(p)+" ");

        }

    }

    public void preOrder(TreeNode p)

    {

        if(!isEmpty(p))

        {

            System.out.print(data(p)+" ");

            preOrder(p.Lchild);

            preOrder(p.Rchild);

        }

    }

 

    public int countLeaf(TreeNode p)

    {

        if(!isEmpty(p))

        {

            countLeaf(p.Lchild);

            countLeaf(p.Rchild);

            this.count++;

        }

        return this.count;

    }

 

 

    public TreeNode copy(TreeNode p)

    {

        TreeNode s= new TreeNode();

        if(p!= null)

        {

            TreeNode l = copy(p.Lchild);

            TreeNode r = copy(p.Rchild);

            s.Lchild = l;

            s.Rchild = r;

            s.data =p.data;

        }

        return s;

    }

}

class BinTreeMain{

    public static void main(String args[]){

        BirnaryTree tt = new BirnaryTree();

 

        TreeNode a = tt.createBT();

        TreeNode b = tt.createBT();

        TreeNode c = tt.createBT();

        TreeNode d = tt.createBT();

        TreeNode e = tt.createBT();

        TreeNode f = tt.createBT();

        TreeNode g = tt.createBT();

        TreeNode h = tt.createBT();

        TreeNode i = tt.createBT();

        TreeNode j = tt.createBT();

        TreeNode k = tt.createBT();

 

        tt.makeBT(a,b,"A",c);

        tt.makeBT(b,d,"B",e);

        tt.makeBT(c,f,"C",g);

        tt.makeBT(d,h,"D",i);

        tt.makeBT(e,j,"E",null);

        tt.makeBT(f,null,"F",null);

        tt.makeBT(g,k,"G",null);

        tt.makeBT(h,null,"H",null);

        tt.makeBT(i,null,"I",null);

        tt.makeBT(j,null,"J",null);

        tt.makeBT(k,null,"K",null);

 

        System.out.print("중위 :");

        tt.inOrder(a);

        System.out.println();

 

        System.out.print("후위 :");

        tt.postOrder(a);

        System.out.println();

 

        System.out.print("전위 :");

        tt.preOrder(a);

        System.out.println();

 

           

        TreeNode new_a = tt.copy(a);

        System.out.print("copy한 트리의 중위 :");

        tt.inOrder(a);

        System.out.println();

       

        System.out.println("leaf 의 갯수"+tt.countLeaf(a)+"개");

    }

   

}

 
재귀함수 -> 스택