二叉树的三种遍历：先序、中序和后序 - 知乎
此文章为作者本人搬运至该网站。
这里的内容是我的这个文章的节选：
数据结构学习记录：第六章：树和二叉树-CSDN博客
因为这一篇文章内容实在太多，可能导致有些重要内容各位看不到，所以我就把我认为的重要内容给单独开出来。
在这里推荐一下让我茅厕顿开的文章（雾）：
二叉树遍历方法——前、中、后序遍历（图解）_二叉树遍历前序中序后序-CSDN博客
这个文章真的很细致！！！里面几乎每一步都附带了图片，比我有耐心多了，我在有的时候也会因为懒得画图或者别的什么原因而不附带图，只是在这里干讲（这一点我也要注意了啊啊啊），我这里是从遍历原理开始讲的，可能会有些废话，如果想直接知道怎么遍历的可以看上面那个文章。
首先，我想问大家一个问题，
如果只用 走两个结点之间的连线 的方法，来从最上面的根节点走完所有的结点，且结点可以重复走过（废话，怎么可能一笔画完qwq），那么各位会选择什么样的走法？
还是以这棵树为例：
（写到这里我才发现我之前画的二叉树都是带有箭头的！这个问题我之前都没有想到！！！）
也就是说，从结点1，只可以走结点之间的连线，且可以重复走，直至把所有结点走完。
如果按照常规思维来想的话，很容易就能想到如下的走法：
从上到下，从左到右，
先从左边走到底，然后回头，找往右边走的路，最后的顺序是：
1->2->4->5->3->6->7
其中省略了重复走的结点，
如果各位在没了解二叉树的遍历之前，也是和我一样这样想的话，
那么，恭喜你！你已经实现了二叉树先序遍历的思维方法！！！(=・ω・=)
但是二叉树的遍历也有个要求，就是每个结点只能被访问一次（也就是一遍而过），那么该怎么实现呢？
这时候，递归就要派上用场了！！！
敲黑板！！！下面才是真正的重量级！！！
课本中，先序遍历二叉树的操作是这样定义的：
若二叉树为空，则空操作，否则：
①访问根节点；
②先序遍历左子树；
③先序遍历右子树。
在这里可能会有人不是很明白，因为没有附带代码，不过我相信就算贴上代码，各位也不一定看懂这个操作里面到底有几个小操作，那么各位可以先慢慢往下看，下面有个 第一和 第二，就是分别介绍前两个小操作的，而第③个操作，其实和第②个操作原理是一样的，这一点从之前对二叉树的定义就可以看出，左孩子和右孩子都是指针，只不过是名字不一样罢了。 （#）
而这只是其中一步的操作，由于二叉树有很多结点，对每个结点都是这样操作的，那么就会进行数次。
既然有先序遍历，那就会有中序遍历和后序遍历，这两个遍历以及其和先序遍历的区别我们等会再讲。
我们按照这样的操作来对之前那个二叉树来进行实现：
首先，判断二叉树是否为空，很显然不为空，那么我们就开始操作：
第一，访问根节点：
注意！！！在这里，访问根节点只是个抽象的行为，而实际我们可以自定义对该结点的操作，比如输出该结点的数据等。
第二，先序遍历左子树：
子树子树，它是个树，而这里又提到了遍历，还记得我们一开始的操作叫做什么吗？
先序遍历！
那么在访问左子树里面，我们又要开始进行先序遍历的操作，也就是说，我们在进行先序遍历的操作的时候，需要在操作里面再进行一个先序遍历的操作。
这不就是递归的思想吗！
在调用这个函数的时候，调用的代码内容又要再次调用这个函数，而由于函数还是那个函数，所以会在 再次调用函数的时候，里面的代码内容会第三次调用这个函数，直至对调用函数的判断不成立，后依次退出。
这个只是简单的回顾，如果各位对递归还不怎么熟悉的话，可以去搜一下相关内容，比如这些：
递归详解——让你真正明白递归的含义-CSDN博客
一文看懂什么递归（算法小结） - 知乎
讲完了递归的大概思想，我们再回到二叉树这边，而其实把递归运用到二叉树里面也是比较容易理解的。
那么这边，其实所进行的操作已经很清晰了，对于上文中（#）的内容，其实这个算法的操作具体就有两个，一个是访问结点（输出数据），一个是遍历子树（左子树或者右子树），而我们这些过程，也就是不断进行这两个操作。
开始先序遍历左子树后，我们再开始进入先序遍历二叉树的操作：
也就是再次访问根节点，在这里，也就是左边第一个子树的根节点——2
访问完根节点后，再次先序遍历左子树，又是一次递归。
也就是走到4，对4进行访问，访问完之后，再次先序遍历4的左子树，
但是到这里，我们发现，4既没有左子树也没有右子树！！！
还记得我们访问根节点之前的步骤吗？
先对这个二叉树是否为空进行判断！！！
那么由于4的左子树为空，那么就进行空操作，
但是这里的操作还是基于对结点4的先序遍历左子树，也就是第②步操作，现在这个操作结束了（空操作），那么就要开始进行第③步，先序遍历右子树，
其实在这里，我们是第一次开始执行对右子树的先序遍历操作，我们可以先回顾一下之前的所有操作：
这里我用tab缩进来表示递归的次数，图中可以看出已经结束了第四次递归，
这样是不是清晰多了？(=・ω・=)
我们继续进行判断，此时开始遍历以4为结点的右子树，
而显然，右子树也为空树，那么这样的话也同样返回空操作。
此时，我们完成了第三次递归中，对以4为根结点的二叉树的三个操作，那么此时就结束了第三次递归，回到以2为根节点的二叉树的操作。
显然第三次递归的结束，也同样是了这个以2为根节点的二叉树的操作中第②个操作——先序遍历左子树的结束。此时进行第③个操作，先序遍历右子树，
也就是对以5为根节点的子树的操作，此时又进入一次递归。
就这样不断进行操作，直至所有子树都遍历完，那么就结束了对整个二叉树的遍历，这里我就不细写了。
那么这样，这个二叉树的先序遍历的访问结果就是：
1->2->4->5->3->6->7
和上面的常规思想做出来的一样！
这里的内容已经多到让我加了好几个分割线了= =，不过我会把这一段独立成文章发出来的，毕竟这一段也挺重要的。
但是我猜还是会有一些人看不懂，或者说，懂了也不会用，那是因为咱还没切合代码来讲：
课本第129页
这里用到递归的函数就是PreOrderTraverse，但是里面的后面那个参数，也就是Status(*Visit)(TElemType e)，这个其实是指针函数，也就是说，函数名用指针指向，而注释里面也给出了Visit函数的一个例子，直接printf，
那么这个visit也就显而易见了，就是之前所说的访问根结点。
不过还要理解指针函数，多少也有点抽象，所以我在网上找了个比较好理解的：
这个visit函数已经做到极简化了，只是为了让各位理解其本质(〜￣△￣)〜，
同时带上了二叉树的定义代码。
在这里递归的函数就成了PreOrder(T)，对于一开始的T——这个指针来说，它其实就是根节点的指针，而if语句里面的T->lchild，就是根结点的左孩子，同时也是二叉树根结点的左子树的根结点。
其余的原理也就和上面的内容差不多了。
在这里，其实各位有没有意识到，其实递归的思想就和栈的思想差不多！
递归是从这个函数里面再进入这个函数，然后从进入的这个函数里面第二次进入这个函数，直到进入函数的条件不成立，之后则是从最后进入的函数出来，再从倒数第二个进入的函数再出来
是不是符合先进后出，后进先出？
数据结构学习记录：第三章：栈-CSDN博客
（忘了的话可以去补一下前面的文章哦=w=）
那么情况就很简单了，我们可以把上面遍历的过程用递归表示：
在这里，我们把PreOrder()这个函数当作对结点的入栈，当这个结点下面的if语句，一个访问根结点，以及又是两个PreOrder()的函数走完之后（或者直接if不成立），那么这个结点就出栈了，
我这样三言两语的可能讲不清楚，具体可以看这个文章：
二叉树遍历方法——前、中、后序遍历（图解）_二叉树遍历前序中序后序-CSDN博客
这是我第二次安利这个教程了，真的巨详细！！！
在这里我顺便放出文中的非递归版本的二叉树先序遍历：
中序遍历，其实就和先序遍历差不多。
我一列出操作顺序各位应该就明白了：
若二叉树为空，则空操作，否则：
①中序遍历左子树；
②访问根节点；
③中序遍历右子树。
。。。
看清楚了吗？再看一遍先序遍历的操作：
若二叉树为空，则空操作，否则：
①访问根节点；
②先序遍历左子树；
③先序遍历右子树。
。。。
其实道理很简单，中序遍历，只不过是把访问根节点这个操作放在中间罢了。
什么？你问遍历左子树和右子树前面有个先序和中序的文字区别？
在我扎扎实实看了一遍内容后，我可以肯定地告诉你：
这个文字区别，仅仅是文字上的区别！！！
从先序的操作我们已经可以看出，这个遍历的操作只不过是又进入一次递归的函数罢了。
所以在这里我直接放出中序遍历的代码：
从代码里面我们也可以看出，其实先序中序后序遍历什么什么的，只不过是改变了访问根节点的顺序，以及函数名称而已，
实际上二叉树的遍历，一直是遵循从最上面的根节点，先左遍历到底，再一步一步往右边遍历，但是每一次往右边遍历后，都要再往左遍历！！！（易误解！！！）
而代码就留给各位了！各位也可以和我一样跟着代码的顺序一点一点画图并实现操作。
其实也不是因为我懒嘛（
另外，最最重要的是，
其实这三个遍历的内容我看上面那篇文章，用了二十分钟就看懂了，但是要真写出来教程的话，真的要花费不少心思。。。。
而且，这一部分都有比我更好更完善的教程了，我也不用再只用干涩的文字来讲拉～
在这里还是再推荐一下让我茅塞顿开的那篇文章：
二叉树遍历方法——前、中、后序遍历（图解）_二叉树遍历前序中序后序-CSDN博客
同时我也继续放出中序遍历和后续遍历的的代码：（中序遍历非递归）
后序遍历：（递归版）
后序遍历：（非递归）
感兴趣的话可以关注完整内容：
数据结构学习记录：第六章：树和二叉树-CSDN博客
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/1766.html