1. 树的遍历方式
树的遍历是指访问树节点的数据（可以是打印，也可以是做其他的事情）。树的遍历有广度优先与深度优先两大类。
- 广度优先：先处理同一层的兄弟结点（增加宽度），再处理子结点。广度优先遍历又叫层序遍历，是从上往下从左到右的遍历方式。
- 深度优先：先处理子结点（增加深度），再处理同级的兄弟结点。另外，深度优先遍历，根据被遍历结点与其左右子结点的位置，分为三种情况：
- 先序遍历（pre-order）：[DLR]( data, left, right )，先访问结点数据，再递归遍历左子树，然后递归遍历右子树；
- 中序遍历（in-order）：[LDR]( left, data, right )，先递归遍历左子树，再访问结点数据，然后递归遍历右子树；
- 后序遍历（post-order）：[LRD]( left, right, data )，先递归遍历左子树，再递归遍历右子树，最后访问结点数据。
注意：刚学习的时候很容易忘记递归，经常遍历左结点之后立马就回去了，这样会遍历不全。记住，我们是深度优先，只要当前遍历的结点不为null，就继续往下处理子结点，直到遇到null再回归。
1.1 怎样牢记三种遍历方式
- 先左后右——LR：左右子树顺序固定不变。
- x1-L-x2-R-x3，显然看得出，我们可以在x1, x2, x3的任意一个位置上遍历结点本身。在最前边就叫前序遍历，在中间的叫中序遍历，在最后的叫后序遍历。
1.2 遍历示例
我们分别用不同的遍历方式遍历上图二叉树，结果为：
- 层序遍历：3-1-5-2-4；
- 先序遍历：3-1-2-5-4；
- 中序遍历：1-2-3-4-5；
- 后序遍历：2-1-4-5-3.
2. 代码实现
2.1 层序遍历
层序遍历的思路挺有用的，希望大家能熟记，之后在别的地方会用到。
在层序遍历中，当我们遍历完某一层的最后一个结点后，接下来要遍历下一层的第一个结点（假设存在），但这两个结点之间没有一点关系，没有任何连接，怎样才能从上一层的最后一个跳到下一层的第一个呢？
答案是：我们需要借助一种数据结构——队列。我们可以在遍历上一层的每个结点的时候，把该结点的子结点放入队列中，当上一层处理完之后，再从队列里面取出结点就是下一层的结点，且是从左到右的顺序。利用队列先进先出的特性，能保证遍历顺序的正确性。根结点比较特殊，直接入队列即可。
// 遍历：可以对node做任何你想做的事情，这里我们仅仅打印。
private void doSomethingWithNode(Node node) {
System.out.printf("%s\t", node.data);
}
// 层序遍历（广度优先遍历）
public void layerTraversal() {
if (root == null) {
return;
}
// 这里用到自己实现的队列（我会在其他的文章里面详解队列的原理与实现），你可以换成系统自带的。
LinkQueue<Node> queue = new LinkQueue<>();
queue.enqueue(root);
while (!queue.isEmpty()) {
Node node = queue.dequeue();
doSomethingWithNode(node);
if (node.left != null) {
queue.enqueue(node.left);
}
if (node.right != null) {
queue.enqueue(node.right);
}
}
}
2.2 深度优先遍历
我们这里用递归的方式实现，递归出口是node == null。另外，递归都可以转化为非递归，我会单独详细讲述递归与非递归之间的相互转换，这里不再进一步叙述。
核心代码就3行，2行递归调用，一行遍历操作(代码中的doSomethingWithNode)。doSomethingWithNode在最上面，就是先序遍历，在中间就是中序遍历，在最后就是后序遍历。
// 先序遍历
private void preOrder(Node node) {
if (node == null) {
return;
}
doSomethingWithNode(node);
preOrder(node.left);
preOrder(node.right);
}
// 中序遍历
private void inOrder(Node node) {
if (node == null) {
return;
}
inOrder(node.left);
doSomethingWithNode(node);
inOrder(node.right);
}
// 后序遍历
private void postOrder(Node node) {
if (node == null) {
return;
}
postOrder(node.left);
postOrder(node.right);
doSomethingWithNode(node);
}
3. 根据遍历结果把树还原
我们可以根据：中序遍历 + 任意一种其他的遍历，来还原一棵树。拿简单点的中序遍历 + 层序遍历举例：
层序遍历：3-1-5-2-4；中序遍历：1-2-3-4-5。接下来的叙述统一用层序x来表示层序遍历x结点，中序也一样。层序3说明根结点为3，层序1和5表示第2层（即根3的左右孩子）分别为1和5；层序2和4说明2和4在第3层，但无法确定位置，我们再看中序，中序1在2之前，表示2为1的父结点（不可能，因为2在1的下面）或2为1的右结点，所以2为1的右结点。同理，得出4为5的左结点。
4. 遍历的应用
- 前序遍历：1. 打印目录树。 // TODO
- 中序遍历：1. 排序数的顺序输出。// TODO
- 后序遍历：1. 计算目录内的文件大小。 // TODO
源码
转载声明
如果您需要转载，请注明转载来源。
