二叉树定义：

二叉树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于 2 的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具备左右秩序，不能随便颠倒。更多解释，详见堆和堆排序。

一、递归遍历

1、先序遍历

根左右。a，b，d，e，c，f，g

/**
 * 二叉树：先序遍历。根 - 左 - 右
 * 
 * 经典递归写法
 *
 * @author Java 和算法学习：周一
 */
public static void pre(Node head) {if (head == null) {return;}
    System.out.println(head.value);
    pre(head.left);
    pre(head.right);
}

2、中序遍历

左根右。d，b，e，a，f，c，g

/**
 * 二叉树：中序遍历。左 - 根 - 右
 *
 * 经典递归写法
 *
 * @author Java 和算法学习：周一
 */
public static void in(Node head) {if (head == null) {return;}
    in(head.left);
    System.out.println(head.value);
    in(head.right);
}

3、后序遍历

左右根。d，e，b，f，g，c，a

/**
 * 二叉树：后序遍历。左 - 右 - 根
 *
 * 经典递归写法
 *
 * @author Java 和算法学习：周一
 */
public static void pos(Node head) {if (head == null) {return;}
    pos(head.left);
    pos(head.right);
    System.out.println(head.value);
}

经典的递归版先序、中序、后序遍历，咱们再相熟不过了，明天咱们说些不同的，递归序。

认真点的小伙伴仿佛曾经发现，递归的先序、中序、后序遍历其实是很类似的，就是打印的机会不同。这是因为，它们理论是由 递归序 改写而来的。啥是递归序，就是每次通过本人的时候，都打印节点的值，最初打印进去的即是递归序。

在递归序的根底上，只打印第一次通过本人时的值，即是先序；只打印第二次通过本人的值，即是中序；只打印第三次通过本人的值，即是后序。

4、递归序

/**
 * 递归序
 *
 * @author Java 和算法学习：周一
 */
public static void f(Node head) {if (head == null) {return;}
    // 1
    System.out.println(head.value);

    f(head.left);

    // 2
    System.out.println(head.value);

    f(head.right);

    // 3
    System.out.println(head.value);
}

一个论断：已知一个二叉树的先序遍历和后序遍历，某个节点 X，X 先序遍历之前的节点汇合为 A，X 后序遍历之后的节点汇合为 B，那么 A 和 B 的交加肯定是 X 节点的所有先人节点。

二、非递归遍历

1、先序遍历

（1）筹备一个栈，压入以后节点（即头节点）

（2）弹出栈顶元素，打印对应的值

（3）此元素有右孩子往栈压入右孩子，有左孩子往栈压入左孩子（先右再左）

（4）始终执行 2、3 步，直到栈为空。

/**
 * 非递归先序遍历
 *
 * @author Java 和算法学习：周一
 */
public static void pre(Node head) {if (head != null) {Stack<Node> stack = new Stack<>();
        // 压入以后节点
        stack.push(head);
        while (!stack.isEmpty()) {
            // 弹出栈顶元素
            Node current = stack.pop();
            System.out.print(current.value + " ");
            // 先压入右孩子，再压入左孩子
            if (current.right != null) {stack.push(current.right);
            }
            if (current.left != null) {stack.push(current.left);
            }
        }
    }
}

2、中序遍历

（1）筹备一个栈

（2）压入以以后节点 current 为头节点的整个左子树（入栈一个，current 就挪动到左孩子），直到为空

（3）弹出栈顶元素，打印其值，以以后弹出元素的右孩子为 current 节点，反复第 2 步

（4）当栈为空时完结

/**
 * 非递归中序遍历
 *
 * @author Java 和算法学习：周一
 */
public static void in(Node head) {if (head != null) {Stack<Node> stack = new Stack<>();
        Node current = head;
        while (!stack.isEmpty() || current != null) {if (current != null) {
                // 将以后节点的整个左子树入栈
                stack.push(current);
                current = current.left;
            } else {
                // 左子树入栈完后，弹出栈顶元素
                Node pop = stack.pop();
                System.out.print(pop.value + " ");
                // 以以后弹出元素的右孩子为 current 节点，持续循环
                current = pop.right;
            }
        }
    }
}

3、后序遍历

（1）筹备两个栈 stackA，stackB；stackA 压入以后节点（即头节点）

（2）弹出栈顶元素，压入 stackB

（3）此元素有左孩子往 stackA 栈压入左孩子，有右孩子往 stackA 栈压入右孩子（先左再右）

（4）始终执行 2、3 步，直到 stackA 栈为空。

（5）打印所有 stackB 栈的元素

相当于 stackA 出栈程序是 根右左，最初 stackB 出栈程序是 左右根。

/**
 * 非递归后序遍历
 *
 * @author Java 和算法学习：周一
 */
public static void pos(Node head) {if (head != null) {Stack<Node> stackA = new Stack<>();
        Stack<Node> stackB = new Stack<>();
        stackA.push(head);
        while (!stackA.isEmpty()) {
            // stackA 出栈程序是 根 右 左
            Node current = stackA.pop();
            // stackB 入栈程序是 根 右 左
            stackB.push(current);
            // stackA 先左孩子入栈，再右孩子入栈
            if (current.left != null) {stackA.push(current.left);
            }
            if (current.right != null) {stackA.push(current.right);
            }
        }

        // stackB 出栈程序是 左 右 根
        while (!stackB.isEmpty()) {System.out.print(stackB.pop().value + " ");
        }
    }
}

三、二叉树按层遍历

（1）筹备一个队列，头节点入队

（2）出队一个节点，打印其值；出队节点有左孩子则左孩子入队，有右孩子则右孩子入队

（3）循环执行第 2 步，直到队列为空

/**
 * 二叉树按层遍历
 *
 * @author Java 和算法学习：周一
 */
public static void levelTraversal(Node head) {if (head == null) {return;}
    // 筹备一个队列
    Queue<Node> queue = new LinkedList<>();
    // 头节点入队
    queue.offer(head);
    while (!queue.isEmpty()) {
        // 从队列中弹出一个节点
        Node current = queue.poll();
        // 打印
        System.out.print(current.value + " ");
        // 有左孩子则左孩子入队
        if (current.left != null) {queue.offer(current.left);
        }
        // 有右孩子则右孩子入队
        if (current.right != null) {queue.offer(current.right);
        }
    }
}

本文次要介绍了，二叉树的先序、中序、后序的递归遍历（以及已经不晓得的递归序）、非递归遍历，二叉树的层序遍历。

本文全副代码：https://github.com/monday-pro/algorithm-study/tree/master/src/basic/binarytree