已知一棵二叉树的前序遍历序列是ABDGCEFH，其中序遍历序列为DGBAECHF。请画出相应的二叉树，并求出对应此二叉树的后序遍历序列，此二叉树是完全二叉树吗?完全二叉树有什么性质(特点)?

admin2010-04-24 51

问题已知一棵二叉树的前序遍历序列是ABDGCEFH，其中序遍历序列为DGBAECHF。请画出相应的二叉树，并求出对应此二叉树的后序遍历序列，此二叉树是完全二叉树吗?完全二叉树有什么性质(特点)?

选项

答案根据二叉树的遍历规则，前序遍历总是先访问根结点，然后依次遍历其左右子树，而中序遍历规则是先遍历左子树，再访问根结点，然后访问右子树，则由以上规则，我们极易得出此二叉树的根结点是A，中序遍历序列中，根结点左右两边的结果分别属于其左、右子树，所以得出左子树包含3个节点：B，D，G，右子树包含四个结点C，E，F，H。在左子树中，先序遍历序B位于最前，而中序遍历序列中，B位于最后，则可以得出结点B无右子树，只有左子树，又在B的子树中，无论先序遍历还是中序遍历，D都位于G的前面，则G只能是D的右孩子，且D无左孩子，

解析

转载请注明原文地址:https://kaotiyun.com/show/yrAx777K

本试题收录于：数据结构题库理工类分类

数据结构

理工类

相关试题推荐

随机试题

最新回复(0)

已知一棵二叉树的前序遍历序列是ABDGCEFH，其中序遍历序列为DGBAECHF。请画出相应的二叉树，并求出对应此二叉树的后序遍历序列，此二叉树是完全二叉树吗?完全二叉树有什么性质(特点)?

数据结构

理工类

提供数据链路层上的协议转换，在不同或相同的局域网之间存储和转发帧的是()

冲突检测的方法中以硬件技术实现的、最简单的方法是比较接收到的信号的大小。

假设有一个滑动窗口协议使用许多位作为序列号，使得在接收端能分辨出序列中预期新发来的帧编号和那些重发送的老的帧编号。那么，4个窗口边界及窗口大小必须保持什么样的关系?

在数据单元上附加一些数据或是对数据单元作的密码变换，也就是信息的发送者使用公开密钥算法的主要技术产生的别人无法伪造的字符串的行为称作()

下列工作方式中，不属于IMAP4提供的是()

有关WindowsNTServer4．0的主要技术特点的叙述不正确的是()

在推进利率市场化的改革进程中，存、贷款利率市场进行的顺序是_________________________________；先贷款，后存款；先长期、大额，后短期、小额。

________是商业银行出借给贷款对象，并以按约定利率和期限还本付息为条件的货币资金。

通货膨胀条件下财政方面可采取的紧缩政策有

已知二叉树的前序遍历序列HACDFGBE，中序遍历序列为CAFDCHEB，请画出该二叉树，并给出后序遍历序列。

属于清代方论性专著的是

女性卵巢功能成熟，生育能力最旺盛的时期是

全身静脉麻醉药是右旋体药理活性大于左旋体的麻醉药是

心率过快超过170～180次／分时，下列有关心脏变化的描述不正确的是

以下对喹诺酮类抗菌药物的描述不正确的有

某试验室按体积法设计某混凝土配合比，混凝土设计强度等级为C40，强度标准差σ=4．5MPa。可供材料：42．5级硅酸盐水泥，密度ρc=3．1×103kg／m3，富余系数γc=1．16，中砂，表观密度ρs=2．65×103kg／m3，碎石最大粒径为20mm，

化粪池距离地下水取水构筑物不得小于（）m。

唯物辩证法和形而上学斗争的焦点集中在是否承认事物是永恒发展的。()

WherewouldhestayafterhisscholarshipyearinLondonwasover?

Cigarettesaregoodforyourthroat,accordingtoadvertisementsfromhalfacenturyago.Todaysuchclaimsareunthinkable,as