关于二叉树的遍历问题,前序abdgcefh,中序dgbaechf,求后序? 2、前序abdegcfh,中序dbgeachf,求后序?

求大神帮忙,明天考试,有木有简单点的算法
2025-03-05 09:14:35
推荐回答(1个)
回答1:

第一个序列:
1. 前序第一个元素为a,这个元素就是树的根,则在中序中将序列分为dgb和echf,其中第一个序列是a的左子树,第二个序列为a的右子树。
a

dgb echf

2. dgb序列在前序中是bdg,因此b是此子树的根结点,回到中序dgb,b将序列划分为dg和空,所以其左子树为dg 右子树为空
a

b echf

dg

3. dg在前序序列中为dg,所以根结点为d,其划分中序序列dg为空和g两个序列,所以d只有右子树
a

b echf

d

g

4. 同样的方式分析出echf,得二叉树如下,所以后序序列为gdbehfca
a

b c

d e f

g h
同理前序abdegcfh,中序dbgeachf得到的二叉树为:
a
b c
d e f
g h

所以其后序为dgebhfca: