二叉树的先序、中序和后序序列 请构造出该二叉树
问题描述:
二叉树的先序、中序和后序序列 请构造出该二叉树
已知一棵二叉树的先序、中序和后序序列如下,其中各有一部分未给出其值,请构造出该二叉树
先序序列 :A _ C D E F_ H _ J
中序序列 :C _ E D A _ G F I _
后序序列 :C _ _ B H G J I _ _
关键是想看过程
答
先序的第一个为二叉树树根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