先序的第一个为二叉树树根A,因此后序的最后一个也是A 回到中序,以A为根划分,左子树有4个结点,右子树有5个结点 现在看后序:前4个最后的是B,因此先序的第二个是B,并且中序的第二个也是B 简化如下: 先序序列 :A B C D E F_ H _ J 中序序列 :C B E D A _ G F I _ 后序序列 :C _ _ B H G J I _ A 回到先序,A后面连续4个为左子树的先序,因此后面的F就是右子树的根 因此后序的倒数第2个就是F 再利用先序的DE和中序的ED可以得到后序为ED 于是再次简化为: 先序序列 :A B C D E F _ H _ J 中序序列 :C B E D A _ G F I _ 后序序列 :C E D B H G J I F A 现在来看右子树:已知右子树的根为F 从中序可知,F有左右子树,且左右均为2个结点, 从后序序列可知其前的I就是右子树的根,因此,先序J前面的就是I,并且中序最后的就是J
剩下的就可以补充完整了(其实用二叉树的遍历序列也可硬性推导出) 最后结果是: 先序序列 :A B C D E F G H I J 中序序列 :C B E D A H G F I J 后序序列 :C E D B H G J I F A