共计 4518 个字符，预计需要花费 12 分钟才能阅读完成。
二叉树定义：
二叉树（英语：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
