前言

二叉树遍历（Traversing binary tree）是指从根节点触发，按照某种次序依次访问二叉树中所有的结点，使得每个结点被依次访问且仅仅被访问一次。

二叉树的遍历有四种方式，分别为：先序遍历、中序遍历、后序遍历、层次遍历。

一、准备工作

在做实验之前先准备一个二叉树的结构，这样方便进行实验。

（一）定义二叉树的数据结构

package tree; /**  * @Auther: truedei  * @Date: 2020 /20-6-5 11:59  * @Description:  */ public class TreeNode { int val;//每个节点存放的数据         TreeNode left;//左节点         TreeNode right;//右节点 TreeNode(int x) { val = x; } } 

（二）手工构造一个二叉树

至于为什么是手工，因为不想把你搞混了，这篇文章主要是遍历，对于构造二叉树的方法可以自行研究一下。

package tree; /**  * @Auther: truedei  * @Date: 2020 /20-6-7 17:39  * @Description:  */ public class TestTrueDeiTree { public static void main(String[] args) {         TreeNode t1 = new TreeNode(3);         TreeNode t2 = new TreeNode(9);         TreeNode t3 = new TreeNode(20);         TreeNode t4 = new TreeNode(15);         TreeNode t5 = new TreeNode(7);          t1.left=t2;         t1.right=t3;          t3.left=t4;         t3.right=t5; } } 

构造之后的二叉树的结构图：

二、二叉树的遍历讲解

接下来我们这几种遍历算法，一个一个的认识。

四种遍历的概念：

• （1）先序遍历：先访问根节点，再访问左子树，最后访问右子树；可以说为”根-左-右“。
• （2）后序遍历：先左子树，再右子树，最后根节点；可以说为”左-右-根“。
• （3）中序遍历：先左子树，再根节点，最后右子树；可以说为”左-根-右“。
• （4）层序遍历：每一层从左到右访问每一个节点。

（一）前序遍历

1、前序遍历概念

前序遍历：先访问根节点，再访问左子树，最后访问右子树；可以说为”根-左-右“。

按照：先访问根节点，再访问左子树，最后访问右子树的顺序如果用图来描述一下的话，是这样子的;

2、图解前序遍历

1、首先我们有一颗如下所示的二叉树，这就是我们的初始值：

方便理解，为此我做了一个GIF的图：

遍历的顺序：

通过这个规则我们得到前序遍历结果：3、9、20、15、7

3、代码实现前序遍历

（1）递归实现

/** 根-> 左-> 右  * 前序遍历  * @param root  */ public static void PreOrder(TreeNode root) { //结束的条件 if (root==null) return;      System.out.print(root.val+" "); //使用递归进行遍历左孩子 PreOrder(root.left); //递归遍历右孩子 PreOrder(root.right); } 

结果：

3 9 20 15 7

（2）非递归实现

1. 首先申请一个新的栈，记为stack；
2. 声明一个结点treeNode，让其指向root结点；
3. 如果treeNode的不为空，将treeNode的值打印，并将treeNode入栈，然后让treeNode指向treeNode的左结点，
4. 重复步骤3，直到treenode为空；
5. 然后出栈，让treeNode指向treeNode的右孩子
6. 重复步骤3，直到stack为空.

 /**根-->左-->右 * 非递归前序遍历 *  *  * 1，首先申请一个新的栈，记为stack； * 2，声明一个结点treeNode，让其指向node结点； * 3，如果treeNode的不为空，将treeNode的值打印，并将treeNode入栈，然后让treeNode指向treeNode的左结点， * 4，重复步骤3，直到treenode为空； * 5，然后出栈，让treeNode指向treeNode的右孩子 * 6，重复步骤3，直到stack为空. * * @param root */ public static void preOrderStack(TreeNode root){ //利用栈的特性（先进的后出），用于存储节点数据，一层一层的往上冒     Stack<TreeNode> stack = new Stack<>(); //相当于临时的变量，记录当前的所在节点     TreeNode treeNode = root; //两个条件满足一个即可继续执行，退出的条件是当前的节点为null和栈也空了，说明没有数据了 //栈空了说明冒到了最上一层，最上一层也遍历成了，就空了 while (treeNode != null || !stack.isEmpty()){ //迭代访问节点的左孩子，并入栈 //一直遍历最左边的节点 while (treeNode != null){ //先根             System.out.print(treeNode.val+" ");              stack.push(treeNode); //遍历完根，然后还是遍历最左边的。。如果还有的话，还是遍历最左边的             treeNode  = treeNode.left; } //如果节点没有左孩子，则弹出栈顶节点，访问节点右孩子 if(!stack.isEmpty()){             treeNode = stack.pop();             treeNode = treeNode.right; } } } 

4、使用IDEA调试java代码进一步查看执行过程

现在我的代码是这样子的：

package tree; /**  * @Auther: truedei  * @Date: 2020 /20-6-7 17:39  * @Description:  */ public class TestTrueDeiTree { public static void main(String[] args) {         TreeNode t1 = new TreeNode(3);         TreeNode t2 = new TreeNode(9);         TreeNode t3 = new TreeNode(20);         TreeNode t4 = new TreeNode(15);         TreeNode t5 = new TreeNode(7);          t1.left=t2;         t1.right=t3;          t3.left=t4;         t3.right=t5; PreOrder(t1); } /**      * 前序遍历      * @param root      */ public static void PreOrder(TreeNode root) { //先序遍历 if (root==null) return;          System.out.print(root.val+" "); //使用递归进行遍历左孩子 PreOrder(root.left); //递归遍历右孩子 PreOrder(root.right); } } //树结构 class TreeNode { int val;//每个节点存放的数据     TreeNode left;//左节点     TreeNode right;//右节点 TreeNode(int x) { val = x; } } 

为了方便调试，我们先在下面这几个地方打上断点：

第1次：

因为是初次遍历，所以root肯定不为null，所以执行打印的这条语句；

打印了3，就是我们想要的结果

继续调试，更详细的解析，就看图吧：

继续下一步

再次点击下一步之后，传入的是null，所以就不会再继续执行剩下的代码了，

继续点击下一步：

至于为什么会调用执行了遍历右孩子的代码。原因有:
1、程序的代码都是顺序执行的
2、和JVM相关，如果你学过JVM，则这个地方为什么会执行就会很清晰了
3、遍历3的左孩子的结束了，自然而然的销毁了之前的代码，然后就执行到了

继续点下一步，会又一次的进入，并且把20的left节点传入

这个应该就不用多解释了，上面解释的很清楚了

继续下一步会打印出当前节点的值，并调到下一个Debug处

继续下一步会为null，所以退出当前的方法

发现还是为null

再次点击下一步，就会结束掉这次的了

再次点击下一步，会销毁掉刚才运行的方法，回到上一次进入时的状态，这次就该轮到right了

再点一次，main方法也会执行结束，并将其销毁，从而得到了我们想要的结果：

（二）中序遍历

1、中序遍历概念

中序遍历：先左子树，再根节点，最后右子树；可以说为”左-根-右“。

按照：先左子树，再根节点，最后右子树的顺序如果用图来描述一下的话，是这样子的;

2、图解中序遍历

1、首先我们有一颗如下所示的二叉树，这就是我们的初始值：

执行顺序：

3、代码实现中序遍历

（1）递归实现

因为是递归，代码也很简单，修改一下位置就好了。

/** 左-> 根-> 右   * 中序遍历   * @param root  */ public static void MidOrder(TreeNode root) { //先序遍历 if (root==null) return; //使用递归每次都先进行遍历左孩子 MidOrder(root.left);      System.out.print(root.val+" "); //递归遍历右孩子 MidOrder(root.right); } 

（2）非递归实现

1. 申请一个新栈，记为stack，申请一个变量treeNode，初始时令treeNode为头节点；
2. 先把treeNode节点压入栈中，对以treeNode节点为头的整棵子树来说，依次把整棵树的左子树压入栈中，即不断令treeNode=treeNode.leftChild，然后重复步骤2；
3. 不断重复步骤2，直到发现treeNode为空，此时从stack中弹出一个节点记为treeNode，打印node的值，并让treeNode= treeNode.right，然后继续重复步骤2；
4. 当stack为空并且treeNode为空时结束。

 /** 左-->根-->右      * 非递归实现中序遍历      * @param root      */ public static void MidOrderStack(TreeNode root){          Stack<TreeNode> stack = new Stack<TreeNode>();          TreeNode treeNode = root; while(treeNode!=null || !stack.isEmpty()){ while(treeNode != null){                 stack.push(treeNode);                 treeNode = treeNode.left; } if(!stack.isEmpty()){                 treeNode = stack.pop();                 System.out.print(treeNode.val+" ");                 treeNode = treeNode.right; } } } 

4、调试略

整个过程和前序遍历都是差不多的，可以自己试着调试一下，这里就不在啰嗦了。

（三）后序遍历

1、后序遍历概念

后序遍历：先左子树，再右子树，最后根节点；可以说为”左-右-根“。

按照：先左子树，再右子树，最后根节点的顺序如果用图来描述一下的话，是这样子的;

2、图解后序遍历

1、首先我们有一颗如下所示的二叉树，这就是我们的初始值：

遍历到顺序和结果：

动态过程图：

3、代码实现后序遍历

（1）递归实现

 /** 左-->右-->根      * 后序遍历      * @param root      */ public static void BackOrder(TreeNode root) { //先序遍历 if (root==null) return; //使用递归每次都先进行遍历左孩子 BackOrder(root.left); //递归遍历右孩子 BackOrder(root.right); //根         System.out.print(root.val+" "); } 

（2）非递归实现

 /** 左-->右-->根      * 非递归实现后序遍历      * @param root      */ public static void BackOrderStack(TreeNode root){         Stack<TreeNode> stack = new Stack<TreeNode>();         TreeNode treeNode = root;          TreeNode lastVisit = null; //标记每次遍历最后一次访问的节点 //节点不为空，结点入栈，并且指向下一个左孩子 while(treeNode!=null || !stack.isEmpty()){ while(treeNode!=null){                 stack.push(treeNode);                 treeNode = treeNode.left; } //栈不为空 if(!stack.isEmpty()){ //出栈                 treeNode = stack.pop(); /**                  * 这块就是判断treeNode是否有右孩子，                  * 如果没有，则输出treeNode.val，让lastVisit指向treeNode，并让treeNode为空                  * 如果有右孩子，将当前节点继续入栈，treeNode指向它的右孩子,继续重复循环                  */ if(treeNode.right == null || treeNode.right == lastVisit) {                     System.out.print(treeNode.val + " ");                     lastVisit = treeNode;                     treeNode  = null; }else{                     stack.push(treeNode);                     treeNode = treeNode.right; } } } } 

4、调试略

整个过程和前序遍历都是差不多的，可以自己试着调试一下，这里就不在啰嗦了。

（四）层次遍历

1. 首先申请一个新的队列，记为queue；
2. 将根结点root压入queue中；
3. 每次从queue中出队，并赋值给root，作为下一次的根，然后打印root.val的值，如果root左孩子不为空，则将左孩子入队；如果root的右孩子不为空，则将右孩子入队；
4. 重复步骤3，直到queue为空。

/** * 层次遍历 * @param root */ public static void levelOrder(TreeNode root){     LinkedList<TreeNode> queue = new LinkedList<>();          queue.add(root); while(!queue.isEmpty()){         root = queue.pop();         System.out.print(root.val+" "); if(root.left!=null)             queue.add(root.left); if(root.right!=null)             queue.add(root.right); } } 

结果：

3 9 20 15 7 

参考地址：
https://www.cnblogs.com/du001011/p/11229170.html
https://www.cnblogs.com/luoa/p/10839731.html

三、总结

遍历二叉树可以使用递归的方式和非递归的方式来遍历。

四种遍历：

• （1）先序遍历：先访问根节点，再访问左子树，最后访问右子树；可以说为”根-左-右“。
• （2）后序遍历：先左子树，再右子树，最后根节点；可以说为”左-右-根“。
• （3）中序遍历：先左子树，再根节点，最后右子树；可以说为”左-根-右“。
• （4）层序遍历：每一层从左到右访问每一个节点。

所有代码：

package tree; import java.util.LinkedList; import java.util.Stack; /**  * @Auther: truedei  * @Date: 2020 /20-6-7 17:39  * @Description: //preorder，midorder，backorder  */ public class TestTrueDeiTree { public static void main(String[] args) {         TreeNode t1 = new TreeNode(3);         TreeNode t2 = new TreeNode(9);         TreeNode t3 = new TreeNode(20);         TreeNode t4 = new TreeNode(15);         TreeNode t5 = new TreeNode(7);          t1.left=t2;         t1.right=t3;          t3.left=t4;         t3.right=t5;          System.out.println("递归前序遍历："); PreOrder(t1);         System.out.println();         System.out.println("递归中序遍历："); MidOrder(t1);         System.out.println();         System.out.println("递归后序遍历："); BackOrder(t1);          System.out.println();         System.out.println("非递归前序遍历："); preOrderStack(t1);          System.out.println();         System.out.println("非递归中序遍历："); MidOrderStack(t1);          System.out.println();         System.out.println("非递归后序遍历："); BackOrderStack(t1);           System.out.println();         System.out.println("层次遍历："); levelOrder(t1); } /**根-->左-->右      * 递归前序遍历      * @param root      */ public static void PreOrder(TreeNode root) { if (root==null) return;          System.out.print(root.val+" "); //使用递归进行遍历左孩子 PreOrder(root.left); //递归遍历右孩子 PreOrder(root.right); } /**根-->左-->右      * 非递归前序遍历      *      *      * 1，首先申请一个新的栈，记为stack；      * 2，声明一个结点treeNode，让其指向node结点；      * 3，如果treeNode的不为空，将treeNode的值打印，并将treeNode入栈，然后让treeNode指向treeNode的右结点，      * 4，重复步骤3，直到treenode为空；      * 5，然后出栈，让treeNode指向treeNode的右孩子      * 6，重复步骤3，直到stack为空.      *      * @param root      */ public static void preOrderStack(TreeNode root){ //利用栈的特性（先进的后出），用于存储节点数据，一层一层的往上冒         Stack<TreeNode> stack = new Stack<>(); //相当于临时的变量，记录当前的所在节点         TreeNode treeNode = root; //两个条件满足一个即可继续执行，退出的条件是当前的节点为null和栈也空了，说明没有数据了 //栈空了说明冒到了最上一层，最上一层也遍历成了，就空了 while (treeNode != null || !stack.isEmpty()){ //迭代访问节点的左孩子，并入栈 //一直遍历最左边的节点 while (treeNode != null){ //先根                 System.out.print(treeNode.val+" ");                  stack.push(treeNode); //遍历完根，然后还是遍历最左边的。。如果还有的话，还是遍历最左边的                 treeNode  = treeNode.left; } //如果节点没有左孩子，则弹出栈顶节点，访问节点右孩子 if(!stack.isEmpty()){                 treeNode = stack.pop();                 treeNode = treeNode.right; } } } /** 左-->根-->右      * 中序遍历      * @param root      */ public static void MidOrder(TreeNode root) { //先序遍历 if (root==null) return; //使用递归每次都先进行遍历左孩子 MidOrder(root.left);          System.out.print(root.val+" "); //递归遍历右孩子 MidOrder(root.right); } /** 左-->根-->右      * 中序遍历      *      *1. 申请一个新栈，记为stack，申请一个变量treeNode，初始时令treeNode为头节点；      *2. 先把treeNode节点压入栈中，对以treeNode节点为头的整棵子树来说，依次把整棵树的左子树压入栈中，即不断令treeNode=treeNode.leftChild，然后重复步骤2；      *3. 不断重复步骤2，直到发现treeNode为空，此时从stack中弹出一个节点记为treeNode，打印node的值，并让treeNode= treeNode.right，然后继续重复步骤2；      *4. 当stack为空并且treeNode为空时结束。      * @param root      */ public static void MidOrderStack(TreeNode root){          Stack<TreeNode> stack = new Stack<TreeNode>();          TreeNode treeNode = root; while(treeNode!=null || !stack.isEmpty()){ while(treeNode != null){                 stack.push(treeNode);                 treeNode = treeNode.left; } if(!stack.isEmpty()){                 treeNode = stack.pop();                 System.out.print(treeNode.val+" ");                 treeNode = treeNode.right; } } } /** 左-->右-->根      * 后序遍历      * @param root      */ public static void BackOrder(TreeNode root) { //先序遍历 if (root==null) return; //使用递归每次都先进行遍历左孩子 BackOrder(root.left); //递归遍历右孩子 BackOrder(root.right); //根         System.out.print(root.val+" "); } /** 左-->右-->根      * 非递归实现后序遍历      * @param root      */ public static void BackOrderStack(TreeNode root){         Stack<TreeNode> stack = new Stack<TreeNode>();         TreeNode treeNode = root;          TreeNode lastVisit = null; //标记每次遍历最后一次访问的节点 //节点不为空，结点入栈，并且指向下一个左孩子 while(treeNode!=null || !stack.isEmpty()){ while(treeNode!=null){                 stack.push(treeNode);                 treeNode = treeNode.left; } //栈不为空 if(!stack.isEmpty()){ //出栈                 treeNode = stack.pop(); /**                  * 这块就是判断treeNode是否有右孩子，                  * 如果没有，则输出treeNode.val，让lastVisit指向treeNode，并让treeNode为空                  * 如果有右孩子，将当前节点继续入栈，treeNode指向它的右孩子,继续重复循环                  */ if(treeNode.right == null || treeNode.right == lastVisit) {                     System.out.print(treeNode.val + " ");                     lastVisit = treeNode;                     treeNode  = null; }else{                     stack.push(treeNode);                     treeNode = treeNode.right; } } } } /**      * 层次遍历      * @param root      */ public static void levelOrder(TreeNode root){         LinkedList<TreeNode> queue = new LinkedList<>();         queue.add(root); while(!queue.isEmpty()){             root = queue.pop();             System.out.print(root.val+" "); if(root.left!=null)                 queue.add(root.left); if(root.right!=null)                 queue.add(root.right); } } } class TreeNode { int val;//每个节点存放的数据     TreeNode left;//左节点     TreeNode right;//右节点 TreeNode(int x) { val = x; } } 

四、小郑有话说

如果对你有帮助，可以给你身边的朋友。或者给俺点个大大的赞和大大的评论，和评论就是给我最大的支持，感谢。
水平有限，难免会有疏漏或者书写不合理的地方，欢迎交流讨论。
作者：TrueDei
作者唯一博客ＣＳＤＮ：https://truedei.blog.csdn.net/
转载说明：如需转载请注明原地址和作者名。

如果喜欢我的文章，还没看够可以关注我，我会用心写好每一篇文章。

欢迎大佬们加入在下的小社，在此大家可以放开的交流，共同学习进步：