二叉树遍历分为三种方式：先序遍历、中序遍历，后序遍历

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

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

1、递归遍历

顾名思义，利用递归来遍历二叉树，基本代码如下：

public static void  f(Node head) {
    if (head == null) {
        return;
    }
    //1
    f(head.left);
    //2
    f(head.right);
    //3
}

先了解一下递归序，所谓递归序，就是利用递归访问二叉树时，每个结点被遍历的顺序，按照代码逻辑，我们可以得出上面树的递归序是：1 -> 2 -> 4 -> 4 -> 4 -> 2 -> 5 -> 5 -> 5 -> 2 -> 1 -> 3 -> 6 -> 6 -> 6 -> 3 -> 7 -> 7 -> 7 -> 3 -> 1

怎么得出的呢，我们先遍历头结点，所以递归序第一个是 1，接下来遍历头结点的左孩子 2， 所以递归序第二个是 2，接下来遍历 2 的左孩子 4，所以递归序第三个是 4， 接下来遍历 4 的左孩子，因为 4 的左孩子为 null，没有左孩子，回到 4，所以递归序第四个也是 4，然后遍历 4 的右孩子，右孩子也为 null，再回到 4，所以递归序第 5 个也是 4，4 的左右孩子遍历完，回到 2，所以递归序第六个是 2，接下来遍历 2 的右孩子……

先序遍历：每个结点在递归序中第一次出现时打印就是先序遍历// 1 2 4 5 3 6 7

中序遍历：每个结点在递归序中第二次出现时打印就是中序遍历// 4 2 5 1 6 3 7

后序遍历：每个结点在递归序中第三次出现时打印就是后序遍历// 4 5 2 6 7 3 1

程序运行结果再最后

具体代码：

//先序遍历
public static void preOrderRecur(Node head) {
    if (head == null) {
        return;
    }
    System.out.print(head.value + " ");
    preOrderRecur(head.left);
    preOrderRecur(head.right);
}

//中序遍历
public static void inOrderRecur(Node head) {
    if (head == null) {
        return;
    }
    inOrderRecur(head.left);
    System.out.print(head.value + " ");
    inOrderRecur(head.right);
}

//后序遍历
public static void posOrderRecur(Node head) {
    if (head == null) {
        return;
    }
    posOrderRecur(head.left);
    posOrderRecur(head.right);
    System.out.print(head.value + " ");
}

2、非递归遍历

利用了数据结构：栈

2.1 先序遍历

先序遍历：先遍历头结点，在遍历左孩子，再遍历右孩子，简化：中左右

具体步骤：

1、头结点压栈

2、出栈，出栈时打印结点，同时使出栈结点（第一次出栈就是头结点）的左右孩子进栈，注意进栈顺序，要先进右孩子，再进左孩子（我们要先遍历左孩子，栈是先进后出，所以要先进右孩子）

3、重复步骤 2，直到栈空

具体实现代码：

public static void preOrderUnRecur(Node head) {
    System.out.print("pre-order:");
    if (head != null) {
        Stack<Node> s = new Stack<>();
        s.push(head);
        while (!s.empty()) {
            head = s.pop();
            System.out.print(head.value + " ");
            if (head.right != null) {
                s.push(head.right);
            }
            if (head.left != null) {
                s.push(head.left);
            }
        }
    }
    System.out.println();
}

2.2 后序遍历

后序遍历：左右中

先序遍历顺序为“中左右”，如果先序遍历时孩子结点的进栈顺序互换，也就是先进左孩子，再进右孩子，那么出栈顺序就变成了 “中右左”，反过来就是后序遍历的顺序。要做到反过来，只需把第一个栈的出栈结点全部压入第二个栈，第一个栈空后，第二个栈全部出栈即可。

具体步骤：

1、头结点压入栈 s1

2、s1 执行出栈操作，出栈结点压入栈 s2，同时该结点的左右孩子进栈 s1，先进左，再进右

3、重复步骤 2，直至栈 s1空

4、s2 执行出栈操作

具体实现代码：

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

2.3 中序遍历

中序遍历：左中右

左斜树：所有节点都只有左子树

具体步骤：

1、二叉树中以头结点为头的左斜树进栈（头结点，它的左孩子，左孩子的左孩子……)

2、执行出栈操作，打印出栈结点，同时出栈结点的右孩子进栈

3、重读步骤 2，直到栈为空同时指针指向 null 时结束

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

3、运行结果

public static void main(String[] args) {
    Node head = new Node(1);
    head.left = new Node(2);
    head.right = new Node(3);
    head.left.left = new Node(4);
    head.left.right = new Node(5);
    head.right.left = new Node(6);
    head.right.right = new Node(7);


    // recursive
    System.out.println("=============递归=recursive==============");
    System.out.print("pre-order: ");
    preOrderRecur(head);
    System.out.println();
    System.out.print("in-order: ");
    inOrderRecur(head);
    System.out.println();
    System.out.print("pos-order: ");
    posOrderRecur(head);
    System.out.println();

    // unrecursive
    System.out.println("===========非递归=unrecursive=============");
    preOrderUnRecur(head);
    inOrderUnRecur(head);
    posOrderUnRecur(head);

}