import java.util.Stack;

public class BinaryTree {
    private class Node {
        int val;
        Node left;
        Node right;
        Node(int val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
    }

    public Node root;

    public Node creatTree() {
        root = 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);
        root.left = node2;
        root.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node4.left = new Node(8);
        node4.right = new Node(9);
        node6.right = new Node(10);
        node7.left = new Node(11);
        return root;
    }

    public void visit(Node node) {
        if (node == null) return;
        System.out.print(node.val + " ");
    }
    
    // 遞歸前序
    public void preOrder(Node node) {
        if (node == null) return;
        visit(node);
        preOrder(node.left);
        preOrder(node.right);
    }

    // 遞歸中序
    public void inOrder(Node node) {
        if (node == null) return;
        inOrder(node.left);
        visit(node);
        inOrder(node.right);
    }

    // 遞歸后序
    public void postOrder(Node node) {
        if (node == null) return;
        postOrder(node.left);
        postOrder(node.right);
        visit(node);
    }

    // 非遞歸前序
    public void iterPreOrder (Node node) {
        Stack<Node> stack = new Stack<>();
        Node p = node;
        while (p != null || !stack.empty()) {
            // 壓棧到左子樹的最左節(jié)點(diǎn)
            while (p != null) {
                visit(p);       // 在push之前就訪問，其實(shí)是第一次遇到該節(jié)點(diǎn)就訪問
                stack.push(p);
                p = p.left;
            }
            if (!stack.empty()) {
                p = stack.pop();
                p = p.right;
            }
        }
    }

    // 非遞歸中序
    public void iterInOrder (Node node) {
        Stack<Node> stack = new Stack<>();
        Node p = node;
        while (p != null || !stack.empty()) {
            // 壓棧到左子樹的最左節(jié)點(diǎn)
            while (p != null) {
                stack.push(p);
                p = p.left;
            }
            if (!stack.empty()) {
                p = stack.pop();
                visit(p);       // 中序和前序非遞歸僅這一句的位置不同，在pop之后訪問，其實(shí)為第二次遇到時(shí)訪問
                p = p.right;
            }
        }
    }

    // 非遞歸后序
    public void iterPostOrder (Node node) {
        Stack<Node> stack = new Stack<>();
        // 后續(xù)為先左右，后自己豆村。前序和中序的push和pop其實(shí)可以看做是兩次路過該節(jié)點(diǎn)
        // 而后續(xù)為第三次，即經(jīng)過該節(jié)點(diǎn)到左節(jié)點(diǎn)，然后再從左節(jié)點(diǎn)經(jīng)過該節(jié)點(diǎn)到右節(jié)點(diǎn)立膛，之后才是節(jié)點(diǎn)自身
        // 故我們這里設(shè)置一個(gè)last變量，來記錄梯码，是否訪問過該節(jié)點(diǎn)的右節(jié)點(diǎn)
        Node curr = node;
        Node last = null;
        // 壓棧到左子樹的最左節(jié)點(diǎn)
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        while (!stack.empty()) {
            curr = stack.pop();
            // 沒有右子樹或右子樹訪問過時(shí)宝泵，才可以訪問該節(jié)點(diǎn)
            if (curr.right == null || curr.right == last) {
                visit(curr);
                last = curr;
            } else {
                stack.push(curr);
                curr = curr.right;
                while (curr != null) {
                    stack.push(curr);
                    curr = curr.left;
                }
            }
        }
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        Node root = tree.creatTree();
        tree.iterPreOrder(root);
        System.out.println();
        tree.iterInOrder(root);
        System.out.println();
        tree.iterPostOrder(root);
        System.out.println();
        tree.preOrder(root);
        System.out.println();
        tree.inOrder(root);
        System.out.println();
        tree.postOrder(root);
        System.out.println();

    }
}

輸出：

1 2 4 8 9 5 3 6 10 7 11 
8 4 9 2 5 1 6 10 3 11 7 
8 9 4 5 2 10 6 11 7 3 1 
1 2 4 8 9 5 3 6 10 7 11 
8 4 9 2 5 1 6 10 3 11 7 
8 9 4 5 2 10 6 11 7 3 1