对某二叉树进行前序遍历的结果为EBADCFHGIKJ,中序遍历的结果为ABCDEFGHIJK,那后序遍历结果为
答案:1 悬赏:80 手机版
解决时间 2021-03-22 12:06
- 提问者网友:伴风望海
- 2021-03-21 11:12
对某二叉树进行前序遍历的结果为EBADCFHGIKJ,中序遍历的结果为ABCDEFGHIJK,那后序遍历结果为
最佳答案
- 五星知识达人网友:忘川信使
- 2021-03-21 12:21
用前序遍历结果去分割中序遍历结果,还原二叉树,然后再依此写出后序遍历结果。
/
B F
/
A D H
/ /
C G IJK
8.前序遍历第八位为G,同3,无需再分割;
9.前序遍历第九位为I,以I分割中序遍历,得I左子树为空,右子树为JK:
E
/
B F
/
A D H
/ /
C G I
JK
10.前序遍历第十位为K,以K分割中序遍历,得K左子树为J,右子树为空。到此,二叉树被完全还原:
E
/
B F
/
A D H
/ /
C G I
K
/
J
11.根据还原出的二叉树写出后序遍历:ACDBGJKIHFE
- 前序遍历结果第一位为E,说明根节点为E,以E分割中序遍历结果,得左子树为ABCD,右子树为FGHIJK:
E
/
ABCD FGHIJK
前序遍历第二位为B,说明B为左子树父节点,以B分割中序遍历,得A为左子树,CD为右子树:
E
/
B FGHIJK
/
A CD
前序遍历第三位为A,说明A为左节点,但2中B的左子树只有A,所以无需再分割;
前序遍历第四位为D,说明D为C的父节点,据此分割中序遍历,得C为D的左子树:
E
/
B FGHIJK
/
A D
/
C
前序遍历第五位为C,同3,无需再分割;
前序遍历第六位为F,以F分割中序遍历,得F左子树为空,右子树为GHIJK:
E
/
B F
/
A D GHIJK
/
C
前序遍历第七位为H,以H分割中序遍历,得H左子树为G,右子树为IJK:
/
B F
/
A D H
/ /
C G IJK
8.前序遍历第八位为G,同3,无需再分割;
9.前序遍历第九位为I,以I分割中序遍历,得I左子树为空,右子树为JK:
E
/
B F
/
A D H
/ /
C G I
JK
10.前序遍历第十位为K,以K分割中序遍历,得K左子树为J,右子树为空。到此,二叉树被完全还原:
E
/
B F
/
A D H
/ /
C G I
K
/
J
11.根据还原出的二叉树写出后序遍历:ACDBGJKIHFE
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
推荐资讯