大家好，欢迎来到IT知识分享网。

介绍

当我们介绍数组、链表时，为什么没有着重研究他们的遍历过程呢？ 二叉树的遍历又有什么特殊之处？

在计算机程序中，遍历本身是一个线性操作。所以遍历同样具有线性结构的数组或链表，是一件轻而易举的事情。

反观二叉树，是典型的非线性数据结构，遍历时需要把非线性关联的节点转化成一个线性的序列，以不同的方式来遍历，遍历出的序列顺序也不同。

那么，二叉树都有哪些遍历方式呢？

从节点之间位置关系的角度来看，二叉树的遍历分为4种。

1. 前序遍历。

2. 中序遍历。

3. 后序遍历。

4. 层序遍历。

从更宏观的角度来看，二叉树的遍历归结为两大类。

1. 深度优先遍历 （前序遍历、中序遍历、后序遍历）。

2. 广度优先遍历 （层序遍历）。

下面就来具体看一看这些不同的遍历方式。

深度优先遍历

深度优先和广度优先这两个概念不止局限于二叉树，它们更是一种抽象的算法思想，决定了访问某些复杂数据结构的顺序。在访问树、图，或其他一些复杂数据结构时，这两个概念常常被使用到。

所谓深度优先，顾名思义，就是偏向于纵深，“一头扎到底”的访问方式。可能这种说法有些抽象，下面就通过二叉树的前序遍历、中序遍历、后序遍历 ，来看一看深度优先是怎么回事吧。

前序遍历

二叉树的前序遍历，输出顺序是根节点、左子树、右子树。

上图就是一个二叉树的前序遍历，每个节点左侧的序号代表该节点的输

出顺序，详细步骤如下。

1. 首先输出的是根节点1。
2. 由于根节点1存在左孩子，输出左孩子节点2。
3. 由于节点2也存在左孩子，输出左孩子节点4。
4. 节点4既没有左孩子，也没有右孩子，那么回到节点2，输出节点2的右孩子节点5。
5. 节点5既没有左孩子，也没有右孩子，那么回到节点1，输出节点1的 右孩子节点3。
6. 节点3没有左孩子，但是有右孩子，因此输出节点3的右孩子节点6。到此为止，所有的节点都遍历输出完毕。

中序遍历

二叉树的中序遍历，输出顺序是左子树、根节点、右子树。

上图就是一个二叉树的中序遍历，每个节点左侧的序号代表该节点的输出顺序，详细步骤如下。

1. 首先访问根节点的左孩子，如果这个左孩子还拥有左孩子，则继续深入访问下去，一直找到不再有左孩子的节点，并输出该节点。显然，第一个没有左孩子的节点是节点4
2. 依照中序遍历的次序，接下来输出节点4的父节点2。
3. 再输出节点2的右孩子节点5。
4. 以节点2为根的左子树已经输出完毕，这时再输出整个二叉树的根节点1。
5. 由于节点3没有左孩子，所以直接输出根节点1的右孩子节点3。
6. 最后输出节点3的右孩子节点6。

到此为止，所有的节点都遍历输出完毕。

后序遍历

二叉树的后序遍历，输出顺序是左子树、右子树、根节点。

二叉树的前序、中序、后序遍历的代码怎么写呢？ 递归实现

package net.csdn.usermedal.controller; import org.apache.commons.collections4.CollectionUtils; import java.util.LinkedList; /** * Created by haoll on 2022/5/13 */ public class Demo { /** * 二叉树类 */ public static class TreeNode{ private int data; private TreeNode leftNode; private TreeNode rightNode; public TreeNode(int data){ this.data = data; } } /** * 构建二叉树 * @param inputList * @return */ public static TreeNode createBinaryTree(LinkedList<Integer> inputList){ TreeNode node = null; if(CollectionUtils.isEmpty(inputList)){ return null; } Integer data = inputList.removeFirst(); if(data != null){ node = new TreeNode(data); node.leftNode = createBinaryTree(inputList); node.rightNode = createBinaryTree(inputList); } return node; } /** * 二叉树的前序遍历，输出顺序是根节点、左子树、右子树。 * @param treeNode */ public static void preOrderTraveral(TreeNode treeNode){ if(treeNode == null){ return ; } System.out.println(treeNode.data); preOrderTraveral(treeNode.leftNode); preOrderTraveral(treeNode.rightNode); } /** * 二叉树的中序遍历，输出顺序是左子树、根节点、右子树。 * @param treeNode */ public static void inOrderTraveral(TreeNode treeNode){ if(treeNode == null){ return; } inOrderTraveral(treeNode.leftNode); System.out.println(treeNode.data); inOrderTraveral(treeNode.rightNode); } /** * 二叉树的后序遍历，输出顺序是左子树、右子树、根节点 * @param treeNode */ public static void postOrderTraveral(TreeNode treeNode){ if(treeNode == null){ return; } postOrderTraveral(treeNode.leftNode); postOrderTraveral(treeNode.rightNode); System.out.println(treeNode.data); } public static void main(String[] args) { LinkedList<Integer> inputList = new LinkedList<Integer> (Arrays. asList(new Integer[]{3,2,9,null,null,10,null, null,8,null,4})); TreeNode binaryTree = createBinaryTree(inputList); System.out.println(binaryTree); System.out.println("前序遍历"); preOrderTraveral(binaryTree); System.out.println("中序遍历"); inOrderTraveral(binaryTree); System.out.println("后序遍历"); postOrderTraveral(binaryTree); } } 

二叉树用递归方式来实现前序、中序、后序遍历，是最为自然的方式，因此代码也非常简单。

这3种遍历方式的区别，仅仅是输出的执行位置不同：前序遍历的输出在前，中序遍历的输出在中间，后序遍历的输出在最后。

代码中值得注意的一点是二叉树的构建。二叉树的构建方法有很多，这里把一个线性的链表转化成非线性的二叉树，链表节点的顺序恰恰是二叉树前序遍历的顺序。链表中的空值，代表二叉树节点的左孩子或右孩子为空的情况。

在代码的main函数中，通过{3,2,9,null,null,10,null,null,8,null,4}这样一个线性序列，构建成的二叉树如下。

除使用递归以外，二叉树的深度优先遍历还能通过非递归的方式来实现，不过要稍微复杂一些。

绝大多数可以用递归解决的问题，其实都可以用另一种数据结构来解 决，这种数据结构就是栈 。因为递归和栈都有回溯的特性。

如何借助栈来实现二叉树的非递归遍历呢？下面以二叉树的前序遍历为例，看一看具体过程。

1. 首先遍历二叉树的根节点1，放入栈中。

2. 遍历根节点1的左孩子节点2，放入栈中。

3. 遍历节点2的左孩子节点4，放入栈中。

4. 节点4既没有左孩子，也没有右孩子，我们需要回溯到上一个节点2。 可是现在并不是做递归操作，怎么回溯呢？

别担心，栈已经存储了刚才遍历的路径。让旧的栈顶元素4出栈，就可以重新访问节点2，得到节点2的右孩子节点5。

此时节点2已经没有利用价值（已经访问过左孩子和右孩子），节点2出栈，节点5入栈。

5. 节点5既没有左孩子，也没有右孩子，我们需要再次回溯，一直回溯到节点1。所以让节点5出栈。 根节点1的右孩子是节点3，节点1出栈，节点3入栈。

6. 节点3的右孩子是节点6，节点3出栈，节点6入栈。

7. 节点6既没有左孩子，也没有右孩子，所以节点6出栈。此时栈为空，遍历结束。

代码实现

public static void preOrderTraveralWithStack(TreeNode root){ Stack<TreeNode> stack = new Stack<>(); TreeNode treeNode = root; //迭代访问节点的左孩子，并入栈 while (treeNode != null || !stack.isEmpty()){ while (treeNode != null){ System.out.println(treeNode.data); stack.push(treeNode); treeNode = treeNode.leftNode; } //没有左孩子了，弹出栈顶，访问右孩子 if(!stack.isEmpty()){ treeNode = stack.pop(); treeNode = treeNode.rightNode; } } }

广度优先遍历

如果说深度优先遍历是在一个方向上“一头扎到底”，那么广度优先遍历 则恰恰相反：先在各个方向上各走出1步，再在各个方向上走出第2步、第3步……一直到各个方向全部走完。听起来有些抽象，下面让我们通 过二叉树的层序遍历 ，来看一看广度优先是怎么回事。

层序遍历，顾名思义，就是二叉树按照从根节点到叶子节点的层次关 系，一层一层横向遍历各个节点。

上图就是一个二叉树的层序遍历，每个节点左侧的序号代表该节点的输出顺序。 可是，二叉树同一层次的节点之间是没有直接关联的，如何实现这种层序遍历呢

这里同样需要借助一个数据结构来辅助工作，这个数据结构就是队列 。

详细遍历步骤如下。

1. 根节点1进入队列。

2. 节点1出队，输出节点1，并得到节点1的左孩子节点2、右孩子节点 3。让节点2和节点3入队。

3. 节点2出队，输出节点2，并得到节点2的左孩子节点4、右孩子节点 5。让节点4和节点5入队。

4. 节点3出队，输出节点3，并得到节点3的右孩子节点6。让节点6入队。

5. 节点4出队，输出节点4，由于节点4没有孩子节点，所以没有新节点 入队。

6. 节点5出队，输出节点5，由于节点5同样没有孩子节点，所以没有新节点入队。

7. 节点6出队，输出节点6，节点6没有孩子节点，没有新节点入队。到此为止，所有的节点遍历输出完毕。

代码实现

 public static void levelOrderTraversal(TreeNode treeNode){ Queue<TreeNode> queue = new LinkedList<>(); queue.offer(treeNode); while (!queue.isEmpty()){ TreeNode poll = queue.poll(); System.out.println(poll.data); if(poll.leftNode != null){ queue.offer(poll.leftNode); } if(poll.rightNode != null){ queue.offer(poll.rightNode); } } }