二叉树的先序、中序和后序序列 请构造出该二叉树

2023-03-04 21:40

已知一棵二叉树的先序、中序和后序序列如下,其中各有一部分未给出其值,请构造出该二叉树先序序列 :A _ C D E F_ H _ J 中序序列 :C _ E D A _ G F I _ 后序序列 :C _ _ B H G J I _ _ 关键是想看过程
1个回答
先序的第一个为二叉树树根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
相关问答
一个二叉树先序序列中最后一个结点是什么
1个回答2022-12-07 15:17
是这个树的最右下角的结点。
若某非空二叉树的先序序列和后序序列正好相同,则该二叉树的形态是什么?为什么?
2个回答2022-12-14 21:56
若某非空二叉树的先序序列和后序序列正好相同,则该二叉树的形态是空树或是只有根结点的树。因为: 若:根-左-右 == 左-右-根 当且仅当:左子树与右子树都为空树。 扩展资料 非空二叉树主要...
全文
二叉树中,什么是前序,中序。后序!
1个回答2022-09-23 20:15
是三种遍历方法,前序:先根结点后左孩子最后右孩子 中序:先左孩子后根结点最后右孩子 后序:先左孩子后右孩子最后根结点
二叉排序树的构造是唯一的吗
1个回答2022-11-11 07:08
如果约定了构造规则,给定某一个构造的关键字序列,则按次序构造出来肯定是唯一的 如果只是给定初始关键字,并没有约定构造的序列(次序),则不唯一
二叉排序树
1个回答2022-09-16 04:29
二叉树具有以下重要性质: 性质1 二叉树第i层上的结点数目最多为2i-1(i≥1)。 证明:用数学归纳法证明: 归纳基础:i=1时,有2i-1=20=1。因为第1层上只有一个根结点,所以命题成立。 归...
全文
什么是二叉排序树
2个回答2022-07-19 10:09
二叉排序树(Binary Sort Tree),首先它是一棵树,“二叉”这个描述已经很明显了,就是树上的一根树枝开两个叉,于是递归下来就是二叉树了(下图所示),而这棵树上的节点是已经排好序的,具体的...
全文
什么是二叉排序树?
1个回答2022-10-25 05:35
二叉排序树要么是空二叉树,要么具有如下特点: 二叉排序树中,如果其根结点有左子树,那么左子树上所有结点的值都小于根结点的值;二叉排序树中,如果其根结点有右子树,那么右子树上所有结点的值都大小根结点的...
全文
什么叫二叉排序树
2个回答2022-10-26 14:35
1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值; (3)左、右子树也分别为二叉排序树; (4)没有键值相等的结点。
判断:若一个结点是某二叉树的前序遍历序列中的最后一个结点,则它也一定是这颗二叉树的中序遍历序列中的
1个回答2022-09-20 11:14
若一个结点是某二叉树的前序遍历序列中的最后一个结点,则它也一定是这颗二叉树的中序遍历序列中的最后一个结点------此命题是为假。 例: A / B 其前序遍历序列为A-...
全文
任何一颗二叉树的叶子结点在先序、中序、后序遍历序列中的相对次序是什么?
3个回答2022-09-18 20:57
任何一颗二叉树的叶子结点在先序、中序、后序遍历序列中的相对次序是什么,应该是按每一个程序的先后排列吧,不过具体的怎么排列我这边也不太了解,不过哪个叶子还是什么程序,都是按先后排列的。