本帖建议使用浅色模式观看O
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
本帖将二叉树的遍历，所以在食用本帖之前，请先了解二叉树的基本知识，本帖不过多介绍。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
首先，二叉树分别由根节点，左子树和柚子树组成。二叉树的前中后序遍历就是通过以不同的顺序遍历根节点，左子树和柚子树。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二叉树的前序遍历。
首先，前序遍历的顺序是根节点，左子树和右子树。也就是根左右。这里会讲2种方法。
首先构建一棵二叉树（画图网站），这里字母顺序按照树的广度优先遍历顺序构建：
根据“根左右”的遍历顺序，我们先遍历根节点 A ，之后遍历点A的左孩子节点 B ：
之后，由于根节点 B 已经遍历过了，之后我们按照顺序遍历节点 B 的左孩子节点 D ，之后发现节点 D 没有后继结点了，回到节点 B ，然后按顺序遍历右孩子 E ：
之后回到节点 B ，发现也没有可遍历的结点，回到根节点 A 。这时就可以遍历 A 的右孩子 C ，最后遍历最后一个节点 F ：
至此，整个二叉树的前序遍历就结束了，我们得到的前序遍历顺序为“ABDECF”。通过观察上图，我们可以发现箭头像是围了整个二叉树一圈，所以我们就可以得出简便方法。就是在每个节点的左边画上一个点，然后穿起来。像这样：
这样得出的遍历结果语上述结果相同。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二叉树的中序遍历。
中序遍历呢，他的顺序是左根右。先左子树，然后根节点，然后柚子树。
还是那棵树，首先先遍历左子树。遍历节点 A 的左孩子 B ，再遍历 B 的左孩子 D：
时候按照顺序，遍历根节点 B ：
然后是右节点，遍历节点 E ，然后回到根节点 B ，再回到根节点 A ，按照顺序遍历节点 A ：
最后遍历右子树 的 节点 C 和 F：
最后中序遍历结果为：D B E A C F。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
之后呢有两个简便方法。先讲我再用的吧：
这个简便方法，就是自由落体。顾名思义，就是将每一个节点给他落到地上：
可以看到遍历顺序没有改变。如果使用这种方法的话建议把二叉树画的开一点。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
其次呢，这个方法和上面一样。也是穿起来。不过点点的位置在每个节点的下面：
然后穿起来：
可以看见，穿起来的顺序与上述两种方法相同。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二叉树的后序遍历：
同样的。先了解顺序：后序遍历的顺序是左右根。这里与上面相同。就不多讲了。
后序遍历的简单方法：
同样的。用线穿起来。不过点是在后面：
所以我们可以得出该二叉树后序遍历的结果为：DEBFCADEBFCADEBFCA 。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
真题讲解：
学完了遍历，自然就要做真题。我们可以看这道题：
按照常规的方法。我们会先推出根节点与其左右子树。但是这样一步步推太麻烦了。我们不妨用一个简便的办法：
首先我们将先序遍历竖着写在纸上，再把中序遍历横着写在纸上。具体原因可参考中序遍历的简便方法：
接下来我们像坐标那样把各个点的位置标出来。比如点 DDD 的位置是：
接下来按照此方法还原所有节点的相对位置：
为了方便，接下来我擦掉先序遍历与中序遍历的辅助字母。可以得到这一棵未连线的二叉树：
重点来了。连线的方法。我们很明显可以找到根节点 AAA 。我们在节点 AAA 处做一个辅助线，用于划分左右子树：
链接 AAA 的左右孩子，同样的。按照上述方法在节点 CCC 和节点 BBB 下方作辅助线，找到其左右孩子。以此类推：
所以我们可得还原过后的树为：
求出其后序遍历结果即可。
那么如果是后序遍历与中序遍历呢？我们还是用同样的方法。只不过后序遍历要倒过来竖着写。例如后序遍历为 ACBACBACB ，还原二叉树时应该写作：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
后记：
好的，本帖就结束了。欢迎大家观看。
对了，二叉树真的不是树吗，再此问问大家。
