二叉树的先序、中序和后序序列 请构造出该二叉树
来源:学生作业帮 编辑:搜搜做题作业网作业帮 分类:数学作业 时间:2024/07/29 12:47:38
二叉树的先序、中序和后序序列 请构造出该二叉树
已知一棵二叉树的先序、中序和后序序列如下,其中各有一部分未给出其值,请构造出该二叉树
先序序列 :A _ C D E F_ H _ J
中序序列 :C _ E D A _ G F I _
后序序列 :C _ _ B H G J I _ _
关键是想看过程
已知一棵二叉树的先序、中序和后序序列如下,其中各有一部分未给出其值,请构造出该二叉树
先序序列 :A _ C D E F_ H _ J
中序序列 :C _ E D A _ G F I _
后序序列 :C _ _ B H G J I _ _
关键是想看过程
![二叉树的先序、中序和后序序列 请构造出该二叉树](/uploads/image/z/5097775-31-5.jpg?t=%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%85%88%E5%BA%8F%E3%80%81%E4%B8%AD%E5%BA%8F%E5%92%8C%E5%90%8E%E5%BA%8F%E5%BA%8F%E5%88%97+%E8%AF%B7%E6%9E%84%E9%80%A0%E5%87%BA%E8%AF%A5%E4%BA%8C%E5%8F%89%E6%A0%91)
先序的第一个为二叉树树根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
回到中序,以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
二叉树的先序、中序和后序序列 请构造出该二叉树
一棵二叉树的先序、中序、后序序列如下,其中一部 分未标出,请构造出该二叉树.
已知一棵二叉树的先序序列是ABCDEFG,中序序列为CBEDAFG,请构造出该二叉树.
已知一个二叉树的中序序列和后序序列分别如下,请画出该二叉树.
已知一棵二叉树的中序序列和后序序列,请画出该二叉树 中序序列 DIGJLKBAECHF 后序序列 ILKJGDBEHFC
已知二叉树的中序序列和后序序列均为ABCDEF,则该二叉树的先序序列为
二叉树的后续序列为DCEGBFHKJIA,中序序列为DCBGEAHFIJK,试建立这颗二叉树,画出该二叉树的先序线索二叉
已知一棵二叉树的先序、中序序列如下,画出该二叉树
1.已知一棵二叉树的前序和中序序列,画出该二叉树,并写出该二叉树的后序序列.
二叉树的结点算法设计一个算法,根据一个二叉树结点的先根序列和中根序列构造出该二叉树.假设二叉树是链接表示的,并且任意两个
已知一棵二叉树的中序和前序序列如下,求该二叉树的后序序列,并画出二叉树
假设一棵二叉树的中序序列为DCBGEAHIJK和后序序列为DCEGBFHKJIA,请画出该二叉树?