前言
二叉树作为一种非常基础但十分重要的数据结构，在排序、搜索、编码、甚至文件系统管理等方面都有广泛应用。今天，我想讲讲关于二叉树遍历的那些事儿。为了大家可以清晰地看懂下文中的代码，在此先定义二叉树的数据结构（使用java语言）。
/**
* 二叉树数据结构
*/
private static class TreeNode {
int val;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
深度优先VS广度优先
大的方面来讲呢，二叉树有两种遍历方法——深度优先遍历和广度优先遍历。
深度优先：对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。要特别注意的是，二叉树的深度优先遍历比较特殊，可以细分为先序遍历、中序遍历、后序遍历。深度优先遍历非递归的通用做法是采用栈。
广度优先：从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。广度优先遍历非递归的通用做法是采用队列。
深度优先遍历
深度优先遍历根据根节点和左右子树访问的顺序可以分为先序、中序和后序遍历。
先序遍历
先序遍历：对任一子树，先访问根，然后遍历其左子树，最后遍历其右子树。按照这个规则，可以很容易的写出先序遍历的递归方法。
/**
* 先序遍历二叉树，递归
* @param root
*/
public static void preOrderTraverse(TreeNode root){
if(root == null){
return;
}
System.out.print(root.val + " ");
preOrderTraverse(root.left);
preOrderTraverse(root.right);
}
对于非递归方法，可以描述为：由根节点开始，不断将二叉树的节点压入栈中，然后由栈中取出栈顶节点，并且将该节点的右、左（顺序不可颠倒）子节点压入栈中，循环此过程直至栈为空。 该方法的java代码如下：
/**
* 先序遍历二叉树，非递归
* @param root
*/
public static void preOrderTraverseNoRecursion(TreeNode root){
LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode currentNode = stack.pop();
System.out.print(currentNode.val + " ");
if (currentNode.right != null){
stack.push(currentNode.right);
}
if (currentNode.left != null){
stack.push(currentNode.left);
}
}
System.out.print("\n");
}
中序遍历
中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树。按照这个规则，可以很容易的写出中序遍历的递归方法。
/**
* 中序遍历二叉树，递归
* @param root
*/
public static void inOrderTraverse(TreeNode root){
if(root == null){
return;
}
inOrderTraverse(root.left);
System.out.print(root.val + " ");
inOrderTraverse(root.right);
}
而对于中序遍历，算法可描述为：首先，找到二叉树中最左边的子节点，并依次将节点压入栈中，然后取出栈顶节点，并将该节点的右节点视为新的根节点，重复上述过程，直至节点为空或者栈为空，java代码如下：
/**
* 中序遍历二叉树，非递归
* @param root
*/
public static void inOrderTraverseNoRecursion(TreeNode root){
LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode currentNode = root;
while (currentNode != null || !stack.isEmpty()){
// 一直循环到二叉树最左端的叶子结点（currentNode是null）
if (currentNode != null){
stack.push(currentNode);
currentNode = currentNode.left;
} else{
currentNode = stack.pop();
System.out.print(currentNode.val + " ");
currentNode = currentNode.right;
}
}
System.out.print("\n");
}
后序遍历
后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后再访问根。按照这个规则，可以很容易的写出后序遍历的递归方法。
/**
* 后序遍历二叉树，递归
* @param root
*/
public static void postOrderTraverse(TreeNode root){
if(root == null){
return;
}
postOrderTraverse(root.left);
postOrderTraverse(root.right);
System.out.print(root.val + " ");
}
对于后序遍历的非递归算法，可描述如下：首先，找到二叉树中最左边的子节点，并依次将节点压入栈中，然后取出栈顶节点，判断该节点是否存在右子节点或者该节点是否为其父节点的右子节点，如果为真，则输出节点元素，并更新当前节点和右子节点，循环该过程直至判断条件不满足，然后将该节点的右节点视为新的根节点，重复上述过程，直至节点为空或者栈为空，java代码如下：
/**
* 后序遍历二叉树，非递归
* @param root
*/
public static void postOrderTraverseNoRecursion(TreeNode root){
LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode currentNode = root;
TreeNode rightNode = null;
while (currentNode != null || !stack.isEmpty()){
// 一直循环到二叉树最左端的叶子结点（currentNode是null）
while (currentNode != null){
stack.push(currentNode);
currentNode = currentNode.left;
}
currentNode = stack.pop();
// 当前结点没有右结点或上一个结点（已经输出的结点）是当前结点的右结点，则输出当前结点
while (currentNode.right == null || currentNode.right == rightNode){
System.out.print(currentNode.val + " ");
rightNode = currentNode;
if(stack.isEmpty()){
System.out.println();
return;
}
currentNode = stack.pop();
}
stack.push(currentNode);
currentNode = currentNode.right;
}
}
广度优先遍历
层次遍历
层次遍历指的是将二叉树按层输出。借助队列可以很容易的实现层次优先遍历。算法描述为：由根节点开始，不断将二叉树的节点送至队列中，然后由队列中取出队列头节点，并且将该节点的左、右子节点分别送至队列中，循环此过程直至队列为空。java代码如下：
/**
* 普通层次遍历
* @param root
*/
public static void levelTraverse(TreeNode root){
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while (!queue.isEmpty()){
TreeNode currentNode = queue.poll();
System.out.print(currentNode.val + " ");
if (currentNode.left != null){
queue.add(currentNode.left);
}
if (currentNode.right != null){
queue.add(currentNode.right);
}
}
System.out.println();
}
层次遍历进阶
除了一般的层次遍历，这里再介绍一种面试中常考的层次遍历——按二叉树的层次结构分行输出元素。要实现这种需求，只需要两个指针记录当前行和下一行最右的节点即可。java代码如下：
/**
* 按行打印二叉树
* 算法描述：
* 1. 初始化：将根节点传入队列，last、nlast指针均指向根节点，
* 其中，last指针指向当前行最右侧的元素，nlast指针指向下一行最右侧的元素
* 2. 循环判断队列是否为空，如果不为空，则：
* 2.1: 获取队列头元素p（将其在队列内删除）并打印
* 2.2: 将该节点的左右子树分别压入队列，并更新nlast指针
* 2.3: 判断last指针与p是否相等，如果相等，则换行，并且更新last = nlast
* @param root
* @return
*/
public static void printTreeByRow(TreeNode root){
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
TreeNode last = root;
TreeNode nLast = null;
while (!queue.isEmpty()){
TreeNode p = queue.poll();
System.out.print(p.val + " ");
if (p.left != null){
queue.add(p.left);
nLast = p.left;
}
if (p.right != null){
queue.add(p.right);
nLast = p.right;
}
// 当last == p时代表该换行了
if(last == p){
last = nLast;
System.out.print("\n");
}
}
}
总结
本篇博文主要介绍了二叉树的遍历方法——深度优先和广度优先，掌握二叉树的遍历方法对于栈和队列的使用也很有帮助。
推荐阅读
- 数据结构之二叉树(三)——二叉查找树
- 数据结构之二叉树(四)——AVL树
- 数据结构之二叉树(五)——红黑树(待更新)
写在最后
欢迎大家关注我的个人博客复旦猿。
