摘要
二叉树的遍历可以用递归的方式简单实现，但是递归也有其局限性，所以非递归实现是否可行？下面的文章就会告诉答案。递归的局限性是什么？文章中也会给出作者的理解。
二叉树的遍历有 4 种方式，分别是前序遍历、中序遍历、后序遍历和层序遍历，它们的区别如下表：
| 遍历方法 | 访问顺序 |
|---|---|
| 前序遍历（Preorder Traversal） | 根节点、左子树、右子树 |
| 中序遍历（Inorder Traversal） | 左子树、根节点、右子树 |
| 后序遍历（Postorder Traversal） | 左子树、右子树、根节点 |
| 层序遍历（Level Order Traversal） | 从上到下、从左到右依次访问每一个节点 |
在《数据结构与算法 - 基础（八）遍历二叉树》中使用递归的方式实现这些遍历（递归方法可以看第八期文章），遍历二叉树使用递归方式实现，在代码上会更加简单明了，同时也不能忽视它的缺点（递归的普遍缺点）：
1、 递归是本质是调用自身，那么在时间和空间上需要更多的消耗；
2、 递归思想核心就是把一个问题拆分为多个小问题，多个小问题重叠的部分，就是增加重复计算消耗；
3、 递归实际上是将函数不断地压入栈，那么就会存在栈溢出的情况（递归层级多的情况下）；
那么是否有其他的遍历实现方案？本文就是介绍遍历二叉树的另外一个方案，统称为非递归遍历，了解这个方案的好处有：
1、 多增加一个实现方案，在应用场景中实现时，可以多一个选择；
2、 一个方案本质是解决某方面的思考和逻辑，通过这个方案了解和学习它的思维和逻辑，方面在解决问题时多一个思路；
准备
在实现遍历之前，先要确定二叉树的类结构，类中有 root 来作为根节点，size 记录二叉树中的节点（或元素）数量：
public class BinaryTree<E> implements BinaryTreeInfo {
protected int size;
protected Node<E> root;
}
Node 类中有记录父节点、左子节点、右子节点和存放元素变量这 4 个基本属性：
protected static class Node<E> {
Node<E> parent;
Node<E> left;
Node<E> right;
E element;
}
前序遍历
前序遍历的顺序是根节点、左子树、右子树。这里用堆栈（stack）的数据结构来实现，大致的逻辑是：
1、 将root赋值给node，然后循环；
2、 当node不是null时，打印node，然后将右子节点压入stack，左子节点赋值给node，进行下一个循环；
3、 当stack是null时，退出循环完成遍历；
4、 当stack不为null，node是null时，就从stack中推出一个node；
代码逻辑中需要注意这几点：
1、 root是null时，不可以遍历；
2、 在循环之前，创建stack；
3、 当右子节点不是null时，才能压入stack；
public void preorderTanversal() {
if (root == null) return;
Node<E> node = root;
Stack<Node<E>> stack = new Stack<>();
while (true) {
if (node != null) {
// 访问 node 节点
print(node.element)
// 将右子节点入栈
if (node.right != null) {
stack.push(node.right);
}
// 向左走
node = node.left;
} else if (stack.isEmpty()) {
return;
} else {
// node 为 null，stack 不为空
node = stack.pop();
}
}
}
中序遍历
中序遍历访问的顺序是左子树、根节点、右子树。中序遍历的逻辑是：
1、 从根节点开始，一直向左遍历，将遍历到的节点一次压入stack中；
2、 从stack中推出node，访问node的元素，然后将右子节点赋值给node；
3、 当stack为null时，完成循环；
写代码时需要特别注意的细节，当 node 为 null 时，不能执行压入 stack 操作，中序遍历相对于前序遍历需要多过几遍代码，帮助更好的理解。
public void inorderTraversal() {
if (root == null) return;
Node<E> node = root;
Stack<Node<E>> stack = new Stack<>();
while (true) {
if (node != null) {
stack.push(node);
node = node.left;
} else if (stack.isEmpty()) {
return;
} else {
// node 为 null， stack 不为 null
// 访问 node 节点
node = stack.pop();
print(node.element)
// 让右节点进行中序遍历
node = node.right;
}
}
}
后序遍历
后序遍历的访问顺序是左子树、右子树、根节点。大致的代码逻辑是：
1、 定义变量prev记录上次被stack推出的node，将root压入stack，然后开始循环；
2、 查看stack顶部的node，当node不是叶子节点，prev的父节点不是stack的顶部节点时，就分别将node的左右非空子节点压入stack；
3、 如果2中的条件不满足，那么就推出stack的node赋值给prev，并访问node；
4、 结束循环的条件是stack为null；
这里用变量 prev 目的就是保证压入 stack 中的节点能保证左子节点、右子节点、节点的顺序：
public void postorderTraversal() {
if (root == null) return;
// 记录上一次弹出的节点
Node<E> prev = null;
Stack<Node<E>> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
Node<E> top = stack.peek();
if (top.isLeaf() ||(prev != null && prev.parent == top)) {
prev = stack.pop();
// 访问节点
print(prev.element)
} else {
if (top.right != null) {
stack.push(top.right);
}
if (top.left != null) {
stack.push(top.left);
}
}
}
层序遍历
层序遍历的访问顺序是从根节点开始，从上到下，从左到右依次访问节点，这里用队列的数据结构来处理：
1、 将根节点入队到队列中，以队列不为null为循环条件开始遍历；
2、 队列出队node，访问node，并将node的左右非空子节点入队；
public void leverOrderTraversal() {
if (root == null) return;
Queue<Node<E>> queue = new LinkedList<>();
// 第一节点入队
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
// 访问节点
print(node.element)
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
用队列实现层序遍历的方式是一个非常奇特的点，这样的实现方式值得多看几遍。
总结
- 二叉树的遍历方式都可以用非递归的方式实现；
- 使用栈或者队列的方式，核心目的就是保证它的访问顺序，代码中要特别注意循环的条件；
- 中序遍历和后序遍历是比较难理解，需要多看几遍，层序遍历是非常奇特点切入点，值得多看几遍。