基础知识补充内容 - 图文

后序遍历结果为 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、后根遍历：左—右—根

从规则可以看出：前根序列的第一个值肯定是整个二叉树的根。后根序列的最后一个值肯定是整个二叉树的根。而知道中根序列和前、后根的一个序列后，必然中根序列将分以根分为两个部分：左子树和右子树。这样，在子树里面找到做子树根的那个值，继续分左右子树，这样下去即可确定二叉树的形态。同时，我们可以看到，如果只知道前、后根遍历。不知道中根，则二叉树形态无法唯一确定。