二叉树遍历技巧.docx

二叉树先根序、后根序、中根序遍历的速算法（解题技巧）经过研究我找出了一种不用画图，由先（后）根序遍历和中根序遍历迅速确定遍历结果的办法。谨以此文献给智商与我同级而又不得不研究算法的朋友。抽象思维太差，用例子来说明吧。下面这个是后根遍历的算法。例1：已知某二叉树的先根序遍历为ABCDEFG,中根序遍历为CDBAFEG，则它的后根序遍历为_________解法如下：1、确定树根。由先序遍历知道，树根为A。2、分离左、右子树。由中根序遍历知，A左面的为CDB左子树结点，右面的FEG为右子树结点。把先根序遍历也分成左、右子树结点，BCD、EFG。前根序遍历BCDEFG中根序遍历CDBFEG3、分别把先根序遍历左、右子树结点抄过来，写的时候要从右往左写，本例中，依次写下B、C、D、，E、F、G，结果是DCBGFE。当然不是简单到这种程序。上面只是个原理。抄的过程应该是这样的：盯着前根序的，瞅着中根序的。如果要抄的先根序中的结点在中根序中是最左/右边，则直接抄过来；如果不是，则把这个结点左边的结点先放记在右根序的最左边，然后继续抄。本题的结果是DCB,FGE,A,即DCBFGEA。上面这个例子太短，看不出“猫腻”来。再举个结点多一点儿的。例2：已知某二叉树的先根序遍历为ABCDEFGHIJK,中根序遍历为CEDFBAHKJIG，则它的后根序遍历为_________按上面的方法：前根序遍历BCDEFGHIJK中根序遍历CEDFBHKJIG依次抄得前根序的结点：F、E(E在中根序遍历中不靠边，所以先放在后根遍序历中左子树结点最左边)、D、C同理，把右子树也抄过来。因此，写下结点的过程依次是：如果还是不太懂，你可以试着做一下下面的例子：已知二叉树前序遍历ABCDEFGHIJK，中序遍历CEDFBAHGKJI，求后序遍历。解：(1)以根结点A分左、右子树结点，BCDEFGHIJKCEDFBHGKJI(2)写左子树，盯着前序，从右到左开始写DCB（在中序中，B靠右边，C靠左边，D不靠边。写一个，从中序中抹一个。）因为D在中序遍历中不靠边，所以下一个结点E先搁到最左边（注意，是“搁”，也就是说，不能把E从中序抹去。EDCB因为B已经抹了，F靠右边。于是F仍然按照从右到左的规则，写在D的的左边。EFDCB最后把E加上，左子树OK。右子树仍然从右到写G因为G不靠边，所以下一个结点H先搁在最左边HG然后继续HKJIG于是，结果是EFDCBHKJIGA前根序遍历类似。以上的方法只适用于三层以内的二叉树（含三层）。在选择题中，三层以上二叉树也可用以上方法初步判断正确答案。