树的三种遍历

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()) {
            // 压栈到左子树的最左节点
            while (p != null) {
                visit(p);       // 在push之前就访问，其实是第一次遇到该节点就访问
                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()) {
            // 压栈到左子树的最左节点
            while (p != null) {
                stack.push(p);
                p = p.left;
            }
            if (!stack.empty()) {
                p = stack.pop();
                visit(p);       // 中序和前序非递归仅这一句的位置不同，在pop之后访问，其实为第二次遇到时访问
                p = p.right;
            }
        }
    }

    // 非递归后序
    public void iterPostOrder (Node node) {
        Stack<Node> stack = new Stack<>();
        // 后续为先左右，后自己。前序和中序的push和pop其实可以看做是两次路过该节点
        // 而后续为第三次，即经过该节点到左节点，然后再从左节点经过该节点到右节点，之后才是节点自身
        // 故我们这里设置一个last变量，来记录，是否访问过该节点的右节点
        Node curr = node;
        Node last = null;
        // 压栈到左子树的最左节点
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        while (!stack.empty()) {
            curr = stack.pop();
            // 没有右子树或右子树访问过时，才可以访问该节点
            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