[数据结构与算法]二叉树的三种遍历递归与非递归实现

public class Main8 {
	/*
           1
          2 3
         4 5 6 7
        8 9
	*/
    public static void main(String[] args) {
        Node root = createTwoTree();
        // 前序遍历
        preSort(root);
        System.out.println("==========前序遍历===========");
        preSort2(root);
        System.out.println("==========前序遍历===========");


        // 中序遍历
        inSort(root);
        System.out.println("==========中序遍历===========");
        inSort2(root);
        System.out.println("==========中序遍历===========");

        // 后序遍历
        endSort(root);
        System.out.println("==========后序遍历===========");
        endSort2(root);
        System.out.println("==========后序遍历===========");
    }

    /**
     * 构建二叉树
     * @return
     */
    public static Node createTwoTree(){
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);
        Node node9 = new Node(9);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node4.left = node8;
        node4.right = node9;

        node5.left = null;
        node5.right = null;
        node6.left = null;
        node6.right = null;
        node7.left = null;
        node7.right = null;

        node8.left = null;
        node8.right = null;
        node9.left = null;
        node9.right = null;

        return node1;
    }


    /**
     * 先序遍历
     * @param root
     */
    public static void preSort(Node root){
        if(root != null){
            System.out.print(root.data + " ");
            preSort(root.left);
            preSort(root.right);
        }
    }

    public static void preSort2(Node root){
        Stack<Node> st = new Stack<>();
        Node curr = root;
        while(curr != null || !st.isEmpty()){
            while(curr != null){
                System.out.print(curr.data + " ");
                st.push(curr);
                curr = curr.left;
            }
            Node top = st.pop();
            curr = top.right;
        }
    }


    /**
     * 中序遍历
     * @param root
     */
    public static void inSort(Node root){
        if(root != null){
            inSort(root.left);
            System.out.print(root.data + " ");
            inSort(root.right);
        }
    }

    public static void inSort2(Node root){
        Stack<Node> st = new Stack<>();
        Node curr = root;
        while(curr != null || !st.isEmpty()){
            while(curr != null){
                st.push(curr);
                curr = curr.left;
            }
            Node top = st.pop();
            System.out.print(top.data + " ");
            curr = top.right;
        }
    }



    /**
     * 后续遍历
     * @param root
     */
    public static void endSort(Node root){
        if(root != null){
            endSort(root.left);
            endSort(root.right);
            System.out.print(root.data + " ");
        }
    }

    public static void endSort2(Node root){
        Stack<Node> st = new Stack<>();
        Node curr = root;
        Node pre = null;
        while(curr != null || !st.isEmpty()){
            while(curr != null){
                st.push(curr);
                curr = curr.left;
            }
            Node top = st.peek();
            // 如果右子树不存在 或者 右子树存在，但是已经被访问过
            if(top.right == null || top.right == pre){
                System.out.print(top.data + " ");
                // 记录被访问过
                pre = top;
                //出栈
                st.pop();
            }else{
                // 右子树没有被访问过，则访问
                curr = top.right;
            }
        }
    }
}