树的前序遍历、中序遍历、后序遍历详解
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关系是左右或者左中，排除左右关系（缺乏节点），所以EF关系是左中。
到此得出左⼦树的形状
3.分析右⼦树。HMZ这三个元素在中序遍历（左中右）的顺序是HMZ，在后序遍历（左右中）的顺序是
HZM。根据后序遍历（左右中）的特点，M在尾部，即M是右⼦树的节点。再根据中序遍历（左中右）的特点，确定H（M的前⾯）是右⼦树的左叶⼦，Z（M的后⾯）是右⼦树的右叶⼦。
所以右⼦树的形状
4. 最后得出整棵树的形状

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。