发布时间 : 星期日 文章基础知识补充内容 - 图文更新完毕开始阅读9e0d900290c69ec3d5bb75b2
后序遍历结果为 ABDCHPGEF
前序遍历为： — ＋ a
* b — c d 中序遍历为： a ＋ b * c — d — e / f 后序遍历为： a b c d — * ＋ e
前序遍历结果为 ABDHEICFG 中序遍历结果为 HDBEIACGF 后序遍历结果为 HDIEBGFCA
/ e f f / —
由先序序列ABCDEFGH和中序序列CBEDAGHF恢复二叉树： 方法：
先序序列ABCDEFGH（注：A是根） 中序序列CBEDAGHF A 以A为根的左、右子树先序序列示意图
? 由左子树先序序列：BCDE和左子树中序序列：CBED构造A的左子树
? 同理，由右子树先序序列：FGH和右子树中序序列GHF构造A的右子树：
B C D E F G H
A B C D E
A F G H E H B C F D G
1. 已知某二叉树的其前序遍历序列为1 2 4 3 5 7 6，中序遍历序列为4 2 1 5 7 3 6，求后序遍历序列（4275631）。 2、已知二叉树前序12453，中序42513。求后序。答案(45231)
这样的题怎么解？我们首先得牢记三种递归规则： 1、前根遍历：根—左—右 2、中根遍历：左—根—右 2、后根遍历：左—右—根
从规则可以看出：前根序列的第一个值肯定是整个二叉树的根。后根序列的最后一个值肯定是整个二叉树的根。而知道中根序列和前、后根的一个序列后，必然中根序列将分以根分为两个部分：左子树和右子树。这样，在子树里面找到做子树根的那个值，继续分左右子树，这样下去即可确定二叉树的形态。同时，我们可以看到，如果只知道前、后根遍历。不知道中根，则二叉树形态无法唯一确定。