⼆叉树先根序、后根序、中根序遍历的速算法（解题技巧）  已知⼆叉树的先/后根序遍历和中根序遍历可唯⼀确定⼀棵⼆叉树，数据结构试题中常有已知先(后)根序遍历要求确定后（先）根序遍历题型。⼀般的，我们要按照已知的条件把⼆叉树画出来，再按图写出结果。这样⿇烦的事常让我感到混乱⽽不得不出错。经过研究我出了⼀种不⽤画图，由先（后）根序遍历和中根序遍历迅速确定遍历结果的办法。谨以此⽂献给智商与我同级⽽⼜不得不研究算法的朋友。
抽象思维太差，⽤例⼦来说明吧。下⾯这个是后根遍历的算法。
例1：已知某⼆叉树的先根序遍历为ABCDEFG，中根序遍历为CDBAFEG，则它的后根序遍历为_________
解法如下：
1、确定树根。由先序遍历知道，树根为A。
2、分离左、右⼦树。由中根序遍历知，A左⾯的为CDB左⼦树结点，右⾯的FEG为右⼦树结点。
把先根序遍历也分成左、右⼦树结点，BCD、EFG。
      前根序遍历　BCD EFG
中根序遍历　CDB FEG
3、分别把先根序遍历左、右⼦树结点抄过来，写的时候要从右往左写，本例中，依次写下B、C、D、，E、F、G，结果是DCB GFE。
当然不是简单到这种程序。上⾯只是个原理。抄的过程应该是这样的：盯着前根序的，瞅着中根序的。如果要抄的先根序中的结点在中根序中是最左/右边，则直接抄过来；如果不是，则把这个结点左边的结点先放记在右根序的最左边，然后继续抄。本题的结果是DCB,FGE,A，即DCBFGEA。
上⾯这个例⼦太短，看不出“猫腻”来。再举个结点多⼀点⼉的。
  例2：已知某⼆叉树的先根序遍历为ABCDEFGHIJK，中根序遍历为CEDFBAHKJIG，则它的后根序遍历为_________
  按上⾯的⽅法：
      前根序遍历　BCDEF  GHIJK
      中根序遍历　CEDFB  HKJIG
依次抄得前根序的结点：F、E(E在中根序遍历中不靠边，所以先放在后根遍序历中左⼦树结点最左边)、D、C
先序中序后序遍历二叉树同理，把右⼦树也抄过来。因此，写下结点的过程依次是：
如果还是不太懂，你可以试着做⼀下下⾯的例⼦：
已知⼆叉树前序遍历 ABCDEFGHIJK，中序遍历 CEDFBAHGKJI，求后序遍历。
解：(1)以根结点A分左、右⼦树结点，
BCDEF GHIJK
CEDFB HGKJI
(2)　写左⼦树，盯着前序，从右到左开始写
DCB　（在中序中，B靠右边，C靠左边，D不靠边。写⼀个，从中序中抹⼀个。）
因为D在中序遍历中不靠边，所以下⼀个结点E先搁到最左边（注意，是“搁”，也就是说，不能把E从中序抹去。
E    DCB
因为B已经抹了，F靠右边。于是F仍然按照从右到左的规则，写在D的的左边。
E　FDCB
最后把E加上，左⼦树OK。
右⼦树仍然从右到写
G
因为G不靠边，所以下⼀个结点H先搁在最左边
H          G
然后继续
H          KJIG
于是，结果是
EFDCBHKJIGA　
前根序遍历类似。
以上的⽅法只适⽤于三层以内的⼆叉树（含三层）。在选择题中，三层以上⼆叉树也可⽤以上⽅法初步判断正确答案。

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