树的前序遍历、中序遍历、后序遍历详解.pdf

树树的的前前序序遍遍历历、、中中序序遍遍历历、、后后序序遍遍历历详详解解

1.前前序序遍遍历历

图1

对于当前节点，先输出该节点，然后输出他的左孩⼦，最后输出他的右孩⼦。以图为例，递归的过程如下：

（1）：输出1，接着左孩⼦；

（2）：输出2，接着左孩⼦；

（3）：输出4，左孩⼦为空，再接着右孩⼦；

（4）：输出6，左孩⼦为空，再接着右孩⼦；

（5）：输出7，左右孩⼦都为空，此时2的左⼦树全部输出，2的右⼦树为空，此时1的左⼦树全部输出，接着1的右⼦树；

（6）：输出3，接着左孩⼦；

（7）：输出5，左右孩⼦为空，此时3的左⼦树全部输出，3的右⼦树为空，⾄此1的右⼦树全部输出，结束。

2.中中序序遍遍历历

对于当前结点，先输出它的左孩⼦，然后输出该结点，最后输出它的右孩⼦。以图为例：

（1）：1--2--4，4的左孩⼦为空，输出4，接着右孩⼦；

（2）：6的左孩⼦为空，输出6，接着右孩⼦；

（3）：7的左孩⼦为空，输出7，右孩⼦也为空，此时2的左⼦树全部输出，输出2，2的右孩⼦为空，此时1的左⼦树全部输出，输出

1，接着1的右孩⼦；

（4）：3--5，5左孩⼦为空，输出5，右孩⼦也为空，此时3的左⼦树全部输出，⽽3的右孩⼦为空，⾄此1的右⼦树全部输出，结束。

3.后后序序遍遍历历

对于当前结点，先输出它的左孩⼦，然后输出它的右孩⼦，最后输出该结点。依旧以图为例：

（1）：1-2-4-6-7，7⽆左孩⼦，也⽆右孩⼦，输出7，此时6⽆左孩⼦，⽽6的右⼦树也全部输出，输出6，此时4⽆左⼦树，⽽4

的右⼦树全部输出，输出4，此时2的左⼦树全部输出，且2⽆右⼦树，输出2，此时1的左⼦树全部输出，接着转向右⼦树；

（2）：3-5，5⽆左孩⼦，也⽆右孩⼦，输出5，此时3的左⼦树全部输出，且3⽆右孩⼦，输出3，此时1的右⼦树全部输出，输出1，

结束。

4.根根据据前前序序遍遍历历中中序序遍遍历历推推导导树树的的结结构构

已知：

前序遍历:GDAFEMHZ

中序遍历:ADEFGHMZ

求后序遍历

⾸先，要先画出这棵⼆叉树，怎么画呢？根据⾯说的我们⼀步⼀步来……

1.先看前序遍历，前序遍历第⼀个⼀定是根节点，那么我们可以知道，这棵树的根节点是G，接着，我们看中序遍历中，根节点⼀定是在中

间访问的，那么既然知道了G是根节点，则在中序遍历中找到G的位置，G的左边⼀定就是这棵树的左⼦树，G的右边就是这棵树的右⼦树

了。

2.我们根据第⼀步的分析，⼤致应该知道左⼦树节点有：ADEF，右⼦树的节点有：HMZ。同时，这个也分别是左⼦树和右⼦树的中序遍历

的序列。

3.在前序遍历遍历完根节点后，接着执⾏前序遍历左⼦树，注意，是前序遍历，什么意思？就是把左⼦树当成⼀棵独⽴的树，执⾏前序遍

历，同样先访问左⼦树的根，由此可以得到，左⼦树的根是D，第2步我们已经知道左⼦树是ADEF了，那么在这⼀步得到左⼦树的根是D，

请看第4步。

4.从第2步得到的中序遍历的节点序列中，找到D，发现D左边只有⼀个A，说明D的左⼦树只有⼀个叶⼦节点，D的右边呢？我们可以得到D

的右⼦树有EF，再看前序遍历的序列，发现F在前，也就是说，F是先前序遍历访问的，则得到E是F的左⼦树，只有⼀个叶⼦节点。

5.到这⾥，我们可以得到这棵树的根节点和左⼦树的结构了。如下图：

6.接着看右⼦树，在第2步的右⼦树中序遍历序列中，右⼦树是HMZ三个节点，那么先看前序遍历的序列，先出现的是M，那么M就是右⼦树

的根节点，刚好，HZ在M的左右，分别是它的左⼦树和右⼦树，因此，右⼦树的结构就出来了：

7.到这⾥，我们可以得到整棵树的结构：

5.根根据据树树的的中中序序遍遍历历后后序序遍遍历历推推导导树树的的结结构构

中序遍历：ADEFGHMZ

后序遍历：AEFDHZMG

1..根据后序遍历的特点（左右中），根节点在结尾，确定G是根节点。根据中序遍历的特点（左中右），确定ADEF组成左⼦树，HMZ组成

右⼦树。

2.分析左⼦树。ADEF这四个元素在后序遍历（左右中）中的顺序是AEFD，在中序遍历（左中右）中的顺序是ADEF。根据后序遍历（左右

中）的特点确定D是左⼦树的节点，根据中序遍历（左中右）的特点发现A在D前⾯，所以A是左⼦树的左叶⼦，EF则是左⼦树的右分枝。

EF在后序（左右中）和中序（左中右）的相对位置是⼀样的，所以EF