1 题目
请详细讲解前序遍历，中序遍历和后序遍历。
2 解答 假设给定如下的二叉树，我们通过分析来详细讲解这三种遍历方式。
1：前序遍历
对于当前节点，先输出该节点，然后输出它的左孩子，最后输出它的右孩子。 即根结点 ---> 左子树 ---> 右子树。以上图为例，递归的过程如下：- 首先输出根节点1。
- 输出左儿子2。
- 因为2没有左儿子，所以输出下一个，即输出右儿子5。
- 因为5没有左儿子，所以输出下一个，即输出右儿子8。
- 至此根的左儿子都输出完毕，开始输出它即1的右儿子，右儿子第一个为3。
- 输出3的左儿子6。
- 输出3的右儿子7。
- 至此全部输出完毕，结束。
2：中序遍历
首先遍历左子树，然后访问根结点，最后遍历右子树。若二叉树为空则结束返回。 即左子树---> 根结点 ---> 右子树。以上图为例，对左右子树分别进行左儿子-->自己-->右儿子输出，递归的过程如下：- 首先输出左儿子，因为2没有左儿子，所以输出自己2。
- 准备输出2的右儿子5，若5有左儿子，则输出该元素，现在因为5没有左儿子，所以输出5。
- 输出5的右儿子8。
- 至此左子树输出完毕，输出根节点1。
- 开始输出右子树，因为3有左子树，所以首先输出6，然后输出3。
- 输出3的右子树7。
- 至此全部输出结束。
3：后序遍历
对于当前结点，先输出它的左孩子，然后输出它的右孩子，最后输出该结点。即左子树 ---> 右子树 ---> 根结点 递归的过程如下：- 首先输出左子树，因为2有右孩子5，而5又有右儿子，所以先输出8。
- 输出8之后，输出自己5。
- 然后输出节点2。
- 至此左子树遍历完毕，开始遍历右子树，因为3有左子树，所以输出6，输出右子树7，最后输出自己3。
- 最后输出根节点1。
- 至此全部输出完毕。
4：讲完了左右子树的概念之后，我们根据前序遍历中序遍历推导树的结构。
前序遍历：1 2 5 8 3 6 7
中序遍历：2 5 8 1 6 3 7
- 首先知道前序遍历的第一个节点是根节点1，可以通过该节点1在中序遍历中把子树分成左右子树，即左子树中有2 5 8，右子树中右6 3 7
- 根据前序遍历的特点，我们可以得到2是左子树的根节点。
- 那么5，8的具体的位置，我们无法从前序遍历中得到结果，那么我们是否可以从中序遍历中获取结果呢？根据中序遍历的特点(左儿子-->自己-->右儿子)我们可以得到5是2的右儿子。
- 再来看8，因为5是2的右儿子，所以8不可能是2的儿子，8只能是5的儿子，那么8是5的左儿子还是右儿子呢？假设8是5的左儿子，那么不满足中序遍历的2 5 8，而应该是2 8 5，所以8是5的右儿子。
- 至此左子树的排序完成。
- 再来看右边的6 3 7。
- 根据前序遍历，去掉2 5 8，可得3 6 7，那么3是右子树的根节点。
- 再根据中序遍历的特点，因为右子树是6 3 7，所以6是3的左儿子，7是3的右儿子。
- 至此右子树的分析也结束了。
5：我们根据中序遍历后序遍历推导树的结构。
中序遍历：2 5 8 1 6 3 7
后序遍历：8 5 2 6 7 3 1
根据后序遍历的特点，即根节点是后序遍历的最后一个节点1，可以通过1，在中序遍历中把树分成左子树和右子树，即1的左半部分为左子树2 5 8，右子树6 3 7。
根据后序遍历的特点是左子树-->右子树-->自己，所以8 5 2中2是左子树的根节点。
根据中序遍历，5 8在2的右边，所以只能是2的右子树的元素，又2只会有一个右儿子，所以5是2的右儿子，最后剩下8是5的什么儿子呢？根据中序遍历的特点，若8是5左儿子，那么中序遍历应该是2 8 5，所以8是5的右儿子。
至此1的左子树排序完成。
再看6 3 7，根据后序遍历，可得3是右子树的根节点，再看中序遍历，6 3 7，所以6 7分别是3的左儿子和右儿子。
至此右子树排序完成。
至此我们得到了整棵数的结构。
讲了这么多，希望你们能够理解，好的话请关注一下每日一算法公众号吧～～～
3 代码
扫一扫 关注我的公众号
你的关注是我最大的动力
如果你想要跟大家分享你的文章，欢迎留言投稿~
如果你喜欢，请留下你的赞哦