一、二叉树的结构
我们先来看一下一个二叉树的基本结构。
1 (root)
/ \
(root.left) 2 3 (root.right)
/ \ / \
4 5 6 7
二叉树算是链表结构的一个升级版，它比链表厉害在哪呢？在于链表的节点只有一个下级节点，而二叉树有两个。 一个二叉树的节点，至少会持有两个指针，一个指向它的左孩子，一个指向它的右孩子。我们来看一下二叉树的节点结构：
class TreeNode {
TreeNode left;// 当前节点左子节点
TreeNode right;// 当前节点右子节点
int value;// 数据
}
对于二叉树的结构，我们如何访问到每个节点呢？通常情况下，二叉树有几种遍历方式，先序遍历，中序遍历，后序遍历，层次遍历，对于先中后序遍历，我们可以简单的理解为，都是针对于父节点来说的，就是说，我遍历一棵二叉树的时候，是先访问父节点，再访问左子节点、右子节点，就叫做先序遍历。三个节点中先遍历左子节点，中间遍历父节点，最后遍历右子节点，就是中序遍历。先访问左子节点，再访问右子节点，最后访问父节点，就是后序遍历。层序遍历就是按层，从左到右的顺序遍历节点。那么对于我们给定的这个二叉树结构，先序遍历的结果就为：1，2，4，5，3，6，7，中序遍历的结果就为：4，2，5，1，6，3，7，后序遍历的结果就为：4，5，2，6，7，3，1。层序遍历的结果为：1，2，3，4，5，6，7。
具体到代码上如何实现呢？其实很简单，我们可以通过递归调用来实现。
二、递归遍历二叉树
- 递归先序遍历
// 递归先序遍历二叉树
public void preOrderRecursive(TreeNode root) {
if (root == null) return;// 递归的终止条件
System.out.print(root.value + " ");// 访问左右子节点*之前*，访问当前节点数据并打印
preOrderRecursive(root.left);// 先序遍历左子节点
preOrderRecursive(root.right);// 先序遍历右子节点
}
- 递归中序遍历
// 递归中序遍历二叉树
public void inOrderRecursive(TreeNode root) {
if (root == null) return;// 递归的终止条件
inOrderRecursive(root.left);// 中序遍历左子节点
System.out.print(root.value + " ");// 访问左右子节点*之间*，访问当前节点数据并打印
inOrderRecursive(root.right);// 中序遍历右子节点
}
- 递归后序遍历
// 递归后序遍历二叉树
public void postOrderRecursive(TreeNode root) {
if (root == null) return;// 递归的终止条件
postOrderRecursive(root.left);// 后序遍历左子节点
postOrderRecursive(root.right);// 后序遍历右子节点
System.out.print(root.value + " ");// 访问左右子节点*之后*，访问当前节点数据并打印
}
可以看出，递归遍历二叉树的的方式很简单，那么如果我们不想用递归的方式遍历，该如何做呢？
三、非递归方式遍历二叉树
不啰嗦，我们直接上代码：
- 先序遍历
public void preOrder(TreeNode root) {
if (root == null) return;
System.out.println("binary tree pre order traverse: ");
Stack<TreeNode> stack = new Stack<>();// 通过栈结构，来保存访问信息
stack.push(root);
while (!stack.isEmpty()) {
root = stack.pop();// 当前节点从栈中弹出即访问它
System.out.println("cur = " + root.value);// 打印节点信息
if (root.right != null) {// 因为栈的后进先出特性，我们会把右节点先入栈，保证它在左节点访问之后再访问
stack.push(root.right);
}
if (root.left != null) {// 左节点后压栈，先弹出，保证了 父节点->左节点->右节点的访问顺序
stack.push(root.left);
}
}
}
- 中序遍历
中序遍历也可以理解为图的深度优先遍历（DFS），即针对父节点的左子节点，深入到无路可走了以后，再往回回溯，去探索其他节点。
public void inOrder(TreeNode root) {
if (root == null) return;
System.out.println("binary tree in order traverse: ");
Stack<TreeNode> stack = new Stack<>();// 同样需要一个栈来辅助操作,相比于先序遍历，不会先压栈
while (!stack.isEmpty() || root != null) {
if (root != null) {
stack.push(root);
root = root.left;// 如果节点存在左子节点，会一直先将左子节点压栈，直到没有左节点为止
} else {// 如果当前遍历到的节点没有左子节点了，就弹栈，开始访问左节点
root = stack.pop();
System.out.println("val = " + root.value);// 访问节点信息并打印
root = root.right;// 因为当前节点无左子节点，当前指针会往右子节点前进，然后循环这个过程
}
}
}
- 后序遍历
后序遍历的过程与先序遍历的过程可以理解为是相反的，先序遍历过程为 中->左->右，后序遍历的过程为 左->右->中，我们理解为，把先序遍历的过程倒过来执行，再把左右节点的访问顺序互换，就可以在先序遍历的基础上，实现后序遍历。
public void postOrder(TreeNode root) {
if (root == null) return;
System.out.println("binary tree post order traverse: ");
Stack<TreeNode> stack1 = new Stack<>();// 后序遍历需要两个栈
Stack<TreeNode> stack2 = new Stack<>();// 用来倒置先序遍历的结果
stack1.push(root);
while (!stack1.isEmpty()) {
root = stack1.pop();
stack2.push(root);
if (root.left != null) {// 注意这里与先序遍历不同的在于是先将左节点压栈，即在这里使左右节点的访问顺序互换
stack1.push(root.left);
}
if (root.right != null) {
stack1.push(root.right);
}
}
while (!stack2.isEmpty()) {// 利用栈的后进先出特性，将先序的整个遍历结果倒置，即得到我们想要的后序遍历结果
System.out.println(stack2.pop().value + " ");
}
}
四、层序遍历二叉树
二叉树可以理解为一种特定结构的图，层序遍历即是图的广度优先遍历（BFS）的一种体现。这里我们利用队列这种结构来辅助遍历。队列的特点是先进先出。
public void levelOrder(TreeNode root) {
if (root == null) return;
System.out.println("binary tree level traverse: ");
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
root = queue.poll();// 先进队列的节点先弹出，先访问
System.out.print(root.val + " ");
if (root.left != null) {// 每一个父节点会有左右两个子节点，层次遍历即先访问父节点，然后按从左到右顺序依次访问左右子节点。
queue.offer(root.left);// 左子节点进队列，下一轮循环，即先弹出左子节点，再将左子节点的左右子节点入队列，如此循环，即可实现按层访问所有节点。
}
if (root.right != null) {
queue.offer(root.right);// 右子节点进队列，
}
}
System.out.println();
}
五、总结
本文介绍了二叉树的几种基本遍历方式，并给出了递归与非递归方式遍历的实现代码，通过对于代码的注释来深刻理解二叉树的遍历过程。
