二叉树的先序、中序和后序序列问题已知二叉树的先序、中序和后序序列分别如下,但其中有一些已模糊不清,试构造出该二叉树.先序

首页 > 中学考试杂题 > 题目详情

二叉树的先序、中序和后序序列问题已知二叉树的先序、中序和后序序列分别如下,但其中有一些已模糊不清,试构造出该二叉树.先序

2022-11-16 01:16:58 17次反馈错误加入收藏正确率 : 100%

题目内容：

二叉树的先序、中序和后序序列问题
已知二叉树的先序、中序和后序序列分别如下,但其中有一些已模糊不清,试构造出该二叉树.
先序序列 _BC_EF__
中序序列 BDE_AG_H
后序序列 _DC_GH_A

优质答案解析

王老师

回答题目：2621条

后序最后一个是A,所以A是先序的第一个得到：
先序序列 ABC_EF__
中序序列 BDE_AG_H
后序序列 _DC_GH_A
_____________(A)____________
____________/______________
________(BDE_)_(G_H)________
先序的第二个元素是B,所以B是A的左子树根节点
由中序B在最前,知道其他元素都在B的右子树上
所以,后序序列为(DE_)B(G_H)A,对比已有的后序序列_DC_GH_A
得后序序列为：EDCBGHFA,中序序列为：BDECAGFH
先序序列 ABC_EF__
中序序列 BDECAGFH
后序序列 EDCBGHFA
所以,二叉树为：
_____________(A)_____________
____________/_______________
__________(B)____(F)_________
________________/__________
___________(C)_(G)_(H)_______
___________/_________________
_________(D)_________________
____________________________
__________(E)________________

本题链接：

大家查题吧

首页 > 中学考试杂题 > 题目详情