java实现二叉树的前序、中序、后序以及层序遍历
前言：本文主要探究二叉树遍历的算法，关于二叉树的基础知识可以去看我的这篇文章：《JAVA实现平衡二叉树（AVL）》
数据构建
我们先来构建一颗二叉树的基本模型
先序遍历
规则：先根再左后右（所有子系也遵循该规则）
顺序：ABDGEHCF
作用：在第一次遍历到节点时就执行操作，一般只是想遍历执行操作（或输出结果）可选用先序遍历。
流程图
递归实现
/**
* 前序遍历-递归
* 顺序：根-左-后
*
* @param node
*/
public void preOrder(TreeNode node) {
if (node == null) return;
//打印根节点
printNodeValue(node);
//如果有左节点则打印左节点
if (node.left_child != null) preOrder(node.left_child);
//如果有右节点则打印右节点
if (node.right_child != null) preOrder(node.right_child);
}
递归实现还是比较简单的，先遍历根节点，如果有左节点则先把左节点的子系遍历完，再去遍历右节点。
循环实现
/**
* 前序遍历-非递归
* 顺序：根-左-后
*/
public void preOrderNonRecursion(TreeNode root) {
TreeNode node = root;//记录根节点
Stack<TreeNode> stack = new Stack<>();//构建一个栈
//开始循环,如果当前节点为空或栈为空则结束循环
while (node != null || !stack.empty()) {
//如果当前节点不为空
if (node != null) {
printNodeValue(node);//遍历当前节点
stack.push(node);//将节点压入栈
node = node.left_child;//当前记录的节点该为旧节点的左节点,即下次循环遍历左节点
//如果当前节点为空
} else {
TreeNode pop = stack.pop();//移出栈顶的节点,并返回被移除的节点
node = pop.right_child;//获取被移除节点的右节点,并记录为当前需要遍历的节点
}
}
}
循环实现相较于递归来说比较麻烦，遍历当前节点的左节点很好处理，但是当没有后续子系需要遍历的时候就比较麻烦了，该如何回退到上一节点呢？
? 此时我们需要用到栈（Stack），它的特性是先进后出(FILO, First In Last Out)，先入栈的元素会被压入栈底，入栈出栈都是操作栈顶的数据。
遍历时，我们需要把遍历过的节点压入栈；当节点没有后续子系可遍历时，需要对当前的节点弹出栈，来模拟二叉树回退到上一层级的效果。
当前，我们也可以用双端队列（Deque）来实现这个效果（单端队列只支持一端进另一端出))
/**
* 前序遍历-非递归
* 顺序：根-左-后
*/
public void preOrderNonRecursion(TreeNode root) {
TreeNode node = root;
/**
* 双端队列实现
* 两种思路 模拟栈后入先出
* 1.从头部插入元素从头取出元素
* 2.从尾部插入元素从尾部取出元素
*/
Deque<TreeNode> queue = new ConcurrentLinkedDeque<>();
while (node != null || !queue.isEmpty()) {
if (node != null) {
printNodeValue(node);
queue.offerLast(node);//将节点加入队列的头部
node = node.left_child;
} else {
TreeNode last = queue.pollLast();//移除队列头部的元素
node = last.right_child;
}
}
}
中序遍历
规则：先左再根后右（所有子系也遵循该规则）
顺序：GDBEHACF
作用：对于二分搜索树，中序遍历的操作顺序（或输出结果顺序）是符合从小到大（或从大到小）顺序的，故要遍历输出排序好的结果需要使用中序遍历
流程图
递归实现
/**
* 中序遍历-递归
* 顺序：左-根-后
*
* @param node 当前根系节点
*/
public void middleOrder(TreeNode node) {
if (node == null) return;
if (node.left_child != null) middleOrder(node.left_child);//如果左节点不为空,则继续向左探查
printNodeValue(node);//输出节点值
if (node.right_child != null) middleOrder(node.right_child);//如果右节点不为空,则继续向右探查
}
递归依旧比较简介，这里不详细介绍。
循环实现
/**
* 中序遍历-非递归
* 顺序：左-根-后
*
* @param root 根节点
*/
public void middleOrderNonRecursion(TreeNode root) {
TreeNode node = root;
Stack<TreeNode> stack = new Stack<>();
while (node != null || !stack.empty()) {
//如果node不为空,把node压入栈,并且继续向左探查
if (node != null) {
stack.push(node);
node = node.left_child;
//如果node为空,弹出栈顶的node,并打印该node的值
} else {
TreeNode pop = stack.pop();
printNodeValue(pop);
//如果弹出栈node的右节点不为空,则继续向右探查
if (pop.right_child != null) {
node = pop.right_child;
}
}
}
}
相较于前序，中序遍历只有在探查到树中最左边的节点时才会输出第一个节点。
后序遍历
规则：先左再右后根（所有子系也遵循该规则）
顺序：GDHEBFCA
作用：后续遍历的特点是执行操作时，肯定已经遍历过该节点的左右子节点，故适用于要进行破坏性操作的情况，比如删除所有节点。
流程图
递归实现
/**
* 后序遍历-递归
* 顺序：左-右-根
*
* @param node 当前根系节点
*/
public void postOrder(TreeNode node) {
if (node == null) return;
if (node.left_child != null) postOrder(node.left_child);//如果左节点不为空,则继续向左探查
if (node.right_child != null) postOrder(node.right_child);//如果右节点不为空,则继续向右探查
printNodeValue(node);//输出节点值
}
循环实现
/**
* 后序遍历-非递归
* 顺序：左-右-根
*
* @param root 根节点
*/
public void postOrderNonRecursion(TreeNode root) {
TreeNode node = root;//记录当前检索的节点
TreeNode prev = null;//记录上一次访问过的节点
Stack<TreeNode> stack = new Stack<>();
while (node != null || !stack.isEmpty()) {
//如果node不为空,把node压入栈,并且继续向左探查
if (node != null) {
stack.push(node);
node = node.left_child;
} else {
node = stack.peek();//根系节点记录为堆栈顶部的节点,注意peek()和pop()的区别,peek只获取元素,不弹出栈
if (node.right_child != null && node.right_child != prev) {//如果该节点的右节点不为空,并且没有被访问过
node = node.right_child;//把node记录为node的右子节点,继续向下探寻
} else {//如果右节点为空,或者不为空但是已经访问过
stack.pop();//把该节点弹出
printNodeValue(node);//打印该节点值
prev = node;//把上一次访问过的节点记录为当前检索的节点
node = null;//把当前检索的节点置空(防止重复打印该节点)
}
}
}
}
这里多用了一个变量prev来记录上一次访问过的节点，如果当前节点是第一次访问并且没有后续的子系，则打印出该节点值，并记录该节点。
循环实现二（双栈）
/**
* 后序遍历-非递归-双栈
* 顺序：左-右-根
*
* @param root 根节点
*/
public void postOrderNonRecursion2(TreeNode root) {
TreeNode node = root;//记录当前检索的节点
Stack<TreeNode> stack = new Stack<>();//临时检索栈
Stack<TreeNode> result = new Stack<>();//结果栈
//开始循环,如果当前节点为空或栈为空则结束循环
while (node != null || !stack.isEmpty()) {
//如果当前检索的节点不为空
if (node != null) {
stack.push(node);//将节点压入临时检索栈
result.push(node);//将节点压入结果栈
node = node.right_child;//当前记录的节点改为检索节点的右节点,即下次循环遍历右节点
} else {// 如果当前节点为空
TreeNode pop = stack.pop();//移出栈顶的节点,并返回被移除的节点
node = pop.left_child;//获取被移除节点的左节点,并记录为当前需要遍历的节点
}
}
//循环遍历结果栈,直到栈空
while (!result.isEmpty()) {
printNodeValue(result.pop());
}
}
这种方法实现思路比较取巧，首先前序遍历的顺序为：根-左-右，我们把前序遍历的顺序稍微改变一下：根-右-左，每次遍历出需要打印的节点值，不直接执行打印，而是把该节点存入第二个栈（结果栈）中；当所有节点都检索完毕时，对结果栈中的元素执行出栈并打印，则此时出栈的顺序为：左-右-根。
层序遍历
规则：把二叉树分层，每一层从左到右遍历
顺序：ABCDEFGH
作用：前面所将的前序、中序、后序遍历的策略为DFS（深度优先搜索），而层序遍历策略为BFS （广度优先搜索）。如果我们使用 DFS/BFS 只是为了遍历一棵树、一张图上的所有结点的话，那么 DFS 和 BFS 的能力没什么差别，我们当然更倾向于更方便写、空间复杂度更低的 DFS 遍历。不过，某些使用场景是 DFS 做不到的，只能使用 BFS 遍历。这就是本文要介绍的两个场景：「层序遍历」、「最短路径」。
流程图
虽然 DFS 与 BFS 都是将二叉树的所有结点遍历了一遍，但它们遍历结点的顺序不同。
递归实现
/**
* 层序遍历-递归
* 顺序：按照层次由左向右输出
*
* @param root 当前根系节点
*/
public void levelOrder(TreeNode root) {
if (root == null) return;
int depth = countNodeDepth(root);//计算节点的深度
for (int i = 1; i <= depth; i++) {//从根节点的第一层级开始遍历
levelOrderRecursive(root, i);
}
}
/**
* 递归计算节点的深度
* 如果该节点没有子节点,则深度为0
* 如果有子节点,则深度为左子节点和右子节点的最大值+1
*
* @param cur_node 当前节点
* @return 节点深度
*/
private int countNodeDepth(TreeNode cur_node) {
if (cur_node == null) {
return 0;//当前节点为空则返深度为0
}
//深度为左树和右树中最大深度+1
return 1 + Math.max(countNodeDepth(cur_node.left_child), countNodeDepth(cur_node.right_child));
}
/**
* 递归遍历
*
* @param node 当前节点
* @param level 当前层级
*/
private void levelOrderRecursive(TreeNode node, int level) {
if (node == null || level < 1) return;//当前节点为空或者层级小于1退出递归
if (level == 1) printNodeValue(node);//层级等于1打印当前节点值
//打印下一层级的节点
levelOrderRecursive(node.left_child, level - 1);
levelOrderRecursive(node.right_child, level - 1);
}
节点深度计算
以上图为例，计算根节点A的深度；由图知根节点左树节点有：B、D、E、G、H，右树中节点有：C、F；其中，左树中层级最深的节点为：G、H，层级为3，右树中层级最深的节点为：F，层级为2;由于此树左树比右树深，采用左树中最的深的节点来计算，则根节点A的深度为：节点G（或H）的深度+1（1代表自己本身的层级）。
递归详解
这个算法的思想是：每次for循环都从根部重新去遍历一遍节点，每遍历完一次下一次遍历都往下增加一层，只有当前遍历的层数属于未遍历过的层数的时候，才去打印节点值。
计算结果
A
B
C
D
E
F
G
H
根据上面的算法可以得出一个线性的结果，现在我们增加点难度，让结果变为层级+层级节点的形式。
递归实现二
/**
* 层序遍历-递归
* 顺序：按照层次由左向右输出并返回二维数组
*
* @param root 当前根系节点
*/
public void levelOrderToArray(TreeNode root) {
if (root == null) return;
helper(root, 0);//递归计算层级
printRes(res);//打印结果
}
//根据层级保存遍历的结果
List<List<Integer>> res = new ArrayList<List<Integer>>();
/**
* 递归计算层级,并存入队列
*
* @param node 计算节点
* @param level 节点层级
*/
private void helper(TreeNode node, int level) {
if (res.size() == level) res.add(new ArrayList<Integer>());//动态增加队列长度
res.get(level).add(node.data);//把节点值根据层级储存在队列中
//判断该节点有无左右子树,若有则递归向下计算
if (node.left_child != null) helper(node.left_child, level + 1);
if (node.right_child != null) helper(node.right_child, level + 1);
}
/**
* 打印层级遍历的结果
*
* @param res
*/
private void printRes(List<List<Integer>> res) {
if (res == null || res.size() <= 0) return;
for (int i = 0; i < res.size(); i++)
System.out.println(i + ":" + res.get(i).toString());
}
计算结果
0:[A]
1:[B, C]
2:[D, E, F]
3:[G, H]
算法二相较于一做了一些改动，首先用一个队列保存每次层级遍历的结果，其次递归停止调用的逻辑由进入停止变为停止进入，改进了递归的逻辑，不需要每一次都从根部去遍历；
在执行遍历的时候，会先遍历左子树，再去遍历右子树，并根据层级储存在队列中。
循环实现
/**
* 层序遍历-循环
* 顺序：按照层次由左向右输出
*
* @param root 根节点
*/
public void levelOrderNonRecursion(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque<>();
if (root != null) queue.add(root);//把根节点加入队列
//如果队列不为空则循环继续
while (!queue.isEmpty()) {
TreeNode poll = queue.poll();//队列头节点出队并返回该元素
printNodeValue(poll);//打印节点值
//如果该节点的左右子树不为空则加入队尾
if (poll.left_child != null) queue.add(poll.left_child);
if (poll.right_child != null) queue.add(poll.right_child);
}
}
计算结果
A
B
C
D
E
F
G
H
虽然和递归实现二同样是使用队列储存，但这里执行遍历的顺序为：根-左-右，三个一组，打印完一组再去递归遍历子系；我们尝试把遍历结果也变成层级+层级节点的形式。
循环实现二
/**
* 层序遍历-循环
* 顺序：按照层次由左向右输出并返回二维数组
*
* @param root 根节点
*/
public void levelOrderNonRecursionToArray(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque<>();//临时储存节点的队列
List<List<Integer>> res = new ArrayList<>();//记录遍历结果的集合
if (root != null) queue.add(root);
//如果队列不为空则继续循环
while (!queue.isEmpty()) {
int n = queue.size();//记录队列的长度
List<Integer> level = new ArrayList<>();//储存层级节点值的集合
for (int i = 0; i < n; i++) {
TreeNode poll = queue.poll();//出队并返回出队的元素
level.add(poll.data);//把节点值加入集合
//如果该节点的左右子树不为空则执行入队
if (poll.left_child != null) queue.add(poll.left_child);
if (poll.right_child != null) queue.add(poll.right_child);
}
res.add(level);//把层级结果加入结果集
}
printRes(res);//结束循环打印结果集
}
计算结果
0:[A]
1:[B, C]
2:[D, E, F]
3:[G, H]
原理和层序遍历递归实现二有些相似，和循环一的不同在于while循环里面嵌套了一个for循环，并实时记录下了当前队列的长度，只有在for循环中把当前层级的节点全部出列才会进入下一次while循环。