6. 二叉树的遍历
遍历二叉树指的是按照某种规律以此访问二叉树中所有的节点，实际上就是讲非线性结构的二叉树中的节点排列在一个线性序列的过程。
6. 1 二叉树遍历概述
如果二叉树底层是用顺序存储结构来保存的，那么遍历二叉树中的节点，直接遍历底层数组即可，如果采用的是链式存储结构保存的，那么有深度优先遍历和广度优先遍历两种遍历方法，本文主要介绍链式存储结构的二叉树的遍历。
关于二叉树的构造代码参考二叉树（上）中三叉链表的实现。
采用链表保存二叉树的节点，则有以下两种遍历方式：
- 深度优先遍历：最先访问树中最深层次的节点
- 广度优先遍历：逐层从左到右从上到下以此访问
对于深度优先遍历又分为以下三种遍历方式：
如果以L、D、R分别表示二叉树的左子树、根、右子树，那么根据遍历顺序的不同，三种遍历方式如下：
- 前（先）序遍历：DLR
- 中序遍历：LDR
- 后序遍历：LRD
由于二叉树定义的递归性，所以深度优先遍历可以利用递归性遍历每个节点，可以一棵非空二叉树右根和左右子树三部分组成，分别遍历这三部分，即可对二叉树实现遍历。
同时，递归又可以转换成循环来实现，因此下面分别用两种方法，递归和非递归方式对深度优先遍历的三种遍历方式实现。
6. 2 二叉树的前序遍历
前序遍历是先处理根节点，其遍历顺序如下：
- 访问根节点
- 递归遍历左子树
- 递归遍历右子树
6.2.1 前序遍历的递归实现
/*
* 递归实现前序遍历二叉树
*/
public List<TreeNode> preIterator() {
return preIterator(root);
}
/**
* 以给定节点为根节点进行前序遍历
*
* @param node
* 给定节点
* @return 返回二叉树的节点懂得顺序集合
*/
private List<TreeNode> preIterator(TreeNode node) {
List<TreeNode> list = new ArrayList<TreeNode>();
// 处理根节点
list.add(root);
// 递归处理左子树
if (node.left != null) {
list.addAll(preIterator(node.left));
}
// 递归处理右子树
if (node.right != null) {
list.addAll(preIterator(node.right));
}
return list;
}
6.2.2 前序遍历的非递归实现
/**
* 非递归实现前序遍历
*
* @return 返回按照前序遍历顺序排列的元素的顺序表
*/
public List<TreeNode> preOrder() {
List<TreeNode> list = new ArrayList<TreeNode>();
preOrderTraverse(root, list);
return list;
}
/**
* 先序遍历的非递归实现
*
* @param node
* 以node节点为跟节点进行先序遍历
* @param list
* 将遍历的元素按照遍历顺序存入list中
*/
private void preOrderTraverse(TreeNode node, List<TreeNode> list) {
// 如果要遍历的树的根节点为null，直接返回
if (node == null) {
return;
}
TreeNode current = node;
// 新建一个空栈，保存节点的右子树
Stack s = new Stack<TreeNode>();
while (current != null || !s.isEmpty()) {// 向左走到尽头，退栈访问右子树
while (current != null) {// 向左走到尽头
list.add(current);// 访问左子树
if (node.right != null) {
s.push(current.right);// 如果右子树不为空，将右子树压入栈
}
current = current.left;
}
// 左子树走到尽头后退栈，开始访问右子树
if (!s.isEmpty()) {
current = (TreeNode) s.pop();// 回溯到左子树的父节点，遍历以此父节点为根的右子树
}
}
}
此方法内层循环中，一直沿着根节点向左走，沿途中访问所经过的根节点，并且将这些根节点的非空右子树压入栈中，一直到左子树的根节点为空。此时回溯，将压入栈的右子树的根节点以此取出，然后重复上述步骤，先序遍历右子树，如果堆栈为空，表示此时已经没有右子树需要遍历，此时外层循环结束，对整棵树的遍历结束。由于每个节点仅仅被访问一次，最多是入栈出栈各一次，因此此算法的时间复杂度为T(n) = O(n)。
6. 3 二叉树的中序遍历
中序遍历是先处理左子树，其遍历顺序如下：
- 递归遍历左子树
- 访问根节点
- 递归遍历右子树
6.3.1 中序遍历的递归实现
/**
* 中序遍历
*
* @return 返回中序遍历得到的节点
*/
public List<TreeNode> inIterator() {
return inIterator(root);
}
/**
* 以给定节点为根节点进行中序遍历
*
* @param node
* 给定节点
* @return 返回二叉树的节点懂得顺序集合
*/
private List<TreeNode> inIterator(TreeNode node) {
List<TreeNode> list = new ArrayList<TreeNode>();
// 递归处理左子树
if (node.left != null) {
list.addAll(inIterator(node.left));
}
// 处理根节点
list.add(root);
// 递归处理右子树
if (node.right != null) {
list.addAll(inIterator(node.right));
}
return list;
}
6.3.2 中序遍历的非递归实现
/**
* 非递归实现二叉树的中序遍历
*
* @return 返回按照中序遍历顺序排列的元素的顺序表
*/
public List<TreeNode> inOrder() {
List<TreeNode> list = new ArrayList<TreeNode>();
inOrderTraverse(root, list);
return list;
}
/**
* 以给定节点为根节点进行中序遍历
*
* @param node
* 以node为根节点对二叉树进行中序遍历
* @param list
* 将遍历的元素按照遍历顺序存入list中
*/
private void inOrderTraverse(TreeNode node, List<TreeNode> list) {
// 如果要遍历的树的根节点为null，直接返回
if (node == null) {
return;
}
TreeNode current = node;
// 新建一个空栈，保存根节点
Stack s = new Stack<TreeNode>();
while (current != null || !s.isEmpty()) {
while (current != null) {// 从根节点开始一直向左走
s.push(current);// 将根节点压入栈
current = current.left;
}
if (!s.isEmpty()) {
// 回溯，将栈顶节点弹出
current = (TreeNode) s.pop();
list.add(current);// 访问栈顶元素
current = current.right;// 转向右子节点为根的子树
}
}
}
该方法沿着根节点一直向左走，沿途将根节点都压入栈，直到左子树为空。此时应该弹出上层的父节点访问之，然后转向该节点的右子树进行中序遍历，重复上述步骤。如果堆栈为空，则说明没有更多的子树需要访问了，此时外部循环结束，整棵树的访问结束。inOrderTraverse和PreOrderTraverse的时间复杂度一样，都是T(n) = O(n)。
6. 4 二叉树的后序遍历
后序遍历是最后处理根节点，其遍历顺序如下：
- 递归遍历左子树
- 递归遍历右子树
- 访问根节点
6.4.1 后序遍历的递归实现
/**
* 后序遍历
*
* @return 返回后序遍历得到的节点
*/
public List<TreeNode> postIterator() {
return postIterator(root);
}
/**
* 以给定节点为根节点进行后序遍历
*
* @param node
* 给定节点
* @return 返回二叉树的节点懂得顺序集合
*/
private List<TreeNode> postIterator(TreeNode node) {
List<TreeNode> list = new ArrayList<TreeNode>();
// 递归处理左子树
if (node.left != null) {
list.addAll(postIterator(node.left));
}
// 递归处理右子树
if (node.right != null) {
list.addAll(postIterator(node.right));
}
// 处理根节点
list.add(root);
return list;
}
6.4.2 后序遍历的非递归实现
/**
* 非递归实现二叉树的后序遍历
*
* @return 返回按照后序遍历顺序排列的元素的顺序表
*/
public List<TreeNode> postOrder() {
List<TreeNode> list = new ArrayList<TreeNode>();
postOrderTraverse(root, list);
return list;
}
/**
* 以给定节点为根节点进行后序遍历
*
* @param node
* 以node为根节点对二叉树进行后序遍历
* @param list
* 将遍历的元素按照遍历顺序存入list中
*/
private void postOrderTraverse(TreeNode node, List<TreeNode> list) {
// 如果要遍历的树的根节点为null，直接返回
if (node == null) {
return;
}
TreeNode current = node;
// 新建一个空栈，保存根节点
Stack s = new Stack<TreeNode>();
while(current != null || !s.isEmpty()){
while(current != null){//从根节点向左开始
s.push(current);//将根节点压入栈
if(current.left != null){
current = current.left;//不断将左子节点压入栈
}
else{//如果左子节点不存在，将右子节点压入栈
current = current.right;
}
}
//从根节点向左走到头后访问之
if(!s.isEmpty()){
current = (TreeNode) s.pop();//弹出栈顶元素
list.add(current);//访问栈顶元素
}
//判断上一步最后弹出栈的是右子树还是左子树，如果是右子树，那么只需要访问父节点即可完成对
//以该父节点为跟的子树的访问
while(!s.isEmpty() && ((TreeNode)s.peek()).right == current){
current = (TreeNode) s.pop();
list.add(current);
}
//如果从根节点开始，最后压入栈的不是右子树，那么重复上述步骤，遍历右子树
if(!s.isEmpty()){
current = ((TreeNode)s.peek()).right;
}else{
current = null;
}
}
}
此方法内层第一个循环，沿着根节点向左子树深入，如果左子树为空，则接着向右子树深入，沿途将根节点压入栈，直到访问到叶子节点。第一个判断语句说明应该取出栈顶元素访问，此时栈顶节点为叶子节点或者没有右子树的但分支节点。访问该节点，然后判断上一步最后弹出栈的是右子树还是左子树，如果是右子树，那么只需要访问父节点即可完成对改子树的访问，如果不是右子树，那么访问其父节点的右子树，如果堆栈为空，则说明没有更多的子树需要访问了，此时外部循环结束，整棵树的访问结束。postOrderTraverse和PreOrderTraverse的时间复杂度一样，都是T(n) = O(n)。
6. 5 二叉树的广度优先遍历
二叉树的广度优先遍历有称为按层遍历，整个遍历先遍历根节点（第一层），再遍历根节点的两个子节点（第二层）…….，以此类推，逐层遍历所有节点。
/**
* 广度优先遍历二叉树
*/
public List<TreeNode> breadthFirst() {
// 用一个顺序队列来过滤树中的节点
Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
// 保存树中的节点
List<TreeNode> list = new ArrayList<TreeNode>();
if (root != null) {
// 将根元素加入队列
queue.offer(root);
}
while (!queue.isEmpty()) {
// 将队列中的队头元素加到list中
list.add(queue.peek());
TreeNode node = queue.poll();
// 如果左子节点补位null，添加到队列中
if (node.left != null) {
queue.offer(node.left);
}
// 如果右子节点补位null，添加到队列中
if (node.right != null) {
queue.offer(node.right);
}
}
return list;
}