〔アルゴリズム最適〕再帰的および非再帰的に二叉木の先中後序遍歴を実現する

8136 ワード

import java.util.Stack;

public class PreInPosTraversal {

    public static class Node{
        public int value;
        public Node left;
        public Node right;

        public Node(int data)
        {
            this.value = data;
        }
    }

    /** *        * @param head */
    public static void preOrderRecur(Node head)
    {
        if(head == null)
        {
            return;
        }
        System.out.println(head.value + " ");
        preOrderRecur(head.left);
        preOrderRecur(head.right);
    }

    /** *        * @param head */
    public static void inOrderRecur(Node head)
    {
        if(head == null)
        {
            return;
        }
        inOrderRecur(head.left);
        System.out.println(head.value + " ");
        inOrderRecur(head.right);
    }

    /** *        * @param head */
    public static void posOrderRecur(Node head)
    {
        if(head == null)
        {
            return;
        }
        posOrderRecur(head.left);
        posOrderRecur(head.right);
        System.out.println(head.value + " ");
    }

    /** *          * @param head */
    public static void preOrderUnRecur(Node head)
    {
        System.out.println("pre-order:");
        if (head != null) {
            Stack<Node> stack = new Stack<Node>();
            stack.add(head);
            while (!stack.isEmpty()) {
                head = stack.pop();
                System.out.println(head.value + " ");
                if(head.right != null)
                {
                    stack.push(head.right);
                }
                if(head.left != null)
                {
                    stack.push(head.left);
                }
            }
        }
        System.out.println();
    }

    /** *         * @param head */
    public static void inOrderUnRecur(Node head)
    {
        System.out.println("in-order: ");
        if(head != null)
        {
            Stack<Node> stack = new Stack<Node>();
            while (!stack.isEmpty() || head != null) {
                if(head != null)
                {
                    stack.push(head);
                    head = head.left;
                }
                else
                {
                    head = stack.pop();
                    System.out.println(head.value + " ");
                    head = head.right;
                }
            }
        }
        System.out.println();
    }

    /** *            * *       * @param head */
    public static void posOrderUnRecur1(Node head)
    {
        System.out.println("pos-order: ");
        if(head != null)
        {
            Stack<Node> s1 = new Stack<Node>();
            Stack<Node> s2 = new Stack<Node>();
            s1.push(head);
            while (!s1.isEmpty()) {
                head = s1.pop();
                s2.push(head);
                if(head.left != null)
                {
                    s1.push(head.left);
                }
                if(head.right != null)
                {
                    s1.push(head.right);
                }
            }
            while (!s2.isEmpty()) {
                System.out.println(s2.pop().value + " ");
            }
        }
        System.out.println();
    }

    /** *            * @param h */
    public static void posOrderUnRecur2(Node h)
    {
        System.out.println("pos=order: ");
        if(h != null)
        {
            Stack<Node> stack = new Stack<Node>();
            stack.push(h);
            Node c = null;
            while (!stack.isEmpty()) {
                c = stack.peek();
                if (c.left != null && h != c.left && h != c.right) {
                    stack.push(c.left);
                } else if (c.right != null && h != c.right) {
                    stack.push(c.right);
                } else {
                    System.out.print(stack.pop().value + " ");
                    h = c;
                }
            }
        }
        System.out.println();
    }


}