已知先序序列:ABCDEFGH,中序序列:CDBAFEHG,画出的二叉树是怎样的?
人气:466 ℃ 时间:2020-09-15 09:19:36
解答
由先序可知,A是根,于是在中序中可知CDB在作,FEHG在右:
A
/ \
(CDB) (FEHG)
同理,先序划分成A|BCD|EFGH.在左子树BCD中,因先序可得B是根,右子树EFGH中E是根:
A
/ \
B E
| |
(CD) (FGH)
在B和B的子孙中,由中序序列CDB,可知CD都在B的左子树上.先C后D,可得C是B的左子节点,D是C的右子节点.同理由FGH在中序序列为FEHG可以推出,F在E的左子树上,HG在右子树上:
A
/ \
B E
/ / \
C F (GH)
\
D
同CD的判断过程,不难得出G是E右子节点,H是G左子节点:
A
/ \
B E
/ / \
C F G
\ /
D H
推荐
猜你喜欢
- 四字成语填空()()有序
- 甲、乙两人各有钱若干元,甲拿出1/6给乙后,乙又拿出1/5给甲,这时他们各240元,两人原来各有多少元?
- 10prs/20bags/10boxes/ctn是什么意思?
- “The+单数名词”特指一类事物吗?那么如果我要表达:特指“那一个”呢?
- 为了测量某种液体的比热容,把质量为100g的铜块从沸腾的水中取出(标准大气压),迅速投入质量为100g、温度为10摄氏度的待测液体中,混合后的共同温度是25摄氏度,若不计热量损失,求这种液体的比热容为多少?
- 如图,在正方形ABCD中,对角线2倍根号2,则正方形的边长为?
- 函数y=根号下sinx+根号下tanx的定义域
- 一个三角形和一个平行四边形等底等高,这个平行四边形的面积比三角形的面积大2.6㎡,这个平行四边形的面积是( )㎡.