二叉树定义：
二叉树（英语：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