某二叉树，先序ABDGCEFH,中序DGBAECHF,求后续遍历。 请给予解题思路。
最新回答
爱情的模样
2026-10-22 13:02:04
后序遍历
是：DGBEHFCA个人的解题思路： 先序是ABDGCEFH 中序是DGBAECHF
根据 先序：根左右（DLR） 中序：左根右（LDR）来划分他们 [D是根 L是左 R是右]
可以从先序看出 A是根结点(先序中最左边的就是根结点)
所以中序分为 DGB（左） A（根） ECHF（右）
中序是左根右（LDR）所以 DGB这部分是在A的左子树那边的 而ECHF是在A的右子树那边的
也因此 可以将先序划分为 A （根） BDG（左） CEFH（右）
现在可以画个草图（最好用先序来画草图 分析的时候比较清晰）
A（根）
/ \
BDG CEFH
（左） （右）
然后看先序 先序是根左右（DLR）所以划分出来的BDG里的B是最左边的因此他是A的左子结点
草图变为这样
A（根）
/ \
B CEFH
丨 （右）
DG
（左）
而先序中划分出来的CEFH里面的C也是最左边的 根据根左右（DLR）能得出C是A的右子结点
草图变成这样
A（根）
/ \
B C
丨 丨
DG EFH
（左） （右）
接下来看中序划分出来的DGB 中序是左根右（LDR） 而B是结点 中序里面B的右边没有东西
因此得出 DG是在B的左子树里 B没有右子树
草图变成这样
A（根）
/ \
B C
/ 丨
DG EFH
（左） （右）
再来就是 看DG 根据先序 D在最左边所以是G根结点 （先序是：根左右DLR 熟记~）
又根据中序 G在D的右边 所以G是D的右子树 （中序是：左根右LDR 也要熟记~）
所以草图变成这样
A（根）
/ \
B C
/ 丨
D EFH
\ （右）
G
现在A的左子树部分就都分析出来了~
接下来看A的右子树部分：
根据中序的 ECHF可以划分出 E（左） C（根） HF（右）
所以草图变成这样
A（根）
/ \
B C
/ / \
D E FH
\ （右）
G
接下来看先序中的FH F在最左边 因此F是H的根结点
再看中序的HF H在F的左边 因此H是F的左子树
所以草图变成这样
A（根）
/ \
B C
/ / \
D E F
\ /
G H
这样一来 图就出来了 然后再看后序就很容易了 （做多了这样的题就可以心算出后序了）
后序是 左右根（LRD） 先看最左边 A的左边是B B的左边是D D没有左边了
所以后序的第一个是D 然后看D的右边是G 后序的第二个是G
D和G看完了往上看就是B 这样一来 A的左部分就出来的 后序前三个是DGB（这时不要把A写进去 因为后序是 左右根（LRD） A的右子树部分没出来 所以A作为根是左后写的）
A的右边到了C C的左边是E 所以后序的第四个是E
E没有子树 回到C这里 C的右边有F F的左边有H 所以后序的第五个是H H后边没有了 回到F
F除了左边的H之外没有右子树了 所以后序的第六个是F 然后回到C C的左子树和右子树都出来了 所以后序的第七个是C
这时候 A的左右子树全出来了 他是最后一个 也因为 后序是 左右根(LRD)
所以后序就是DGBEHFCA了
后序根据 左右根(LRD) 也能分为 DGB（左） EHFC（右）A（根）
纯手打~希望能帮到您~！
你随我身却伴他心
2026-08-18 00:15:06
鲜奶千层雪
2026-05-01 00:43:01
http://zhidao.baidu.com/question/94952674.html?oldq=1
吹梦到西洲
2026-03-30 06:55:54
故城旧事
2026-03-03 05:25:04
热门标签
