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

admin2010-04-24 91

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

选项

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

解析

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

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

数据结构

理工类

相关试题推荐

随机试题

最新回复(0)

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

数据结构

理工类

下列不属于物理层协议标准的是()

_______是各个网络节点先声明自己有数据要发送，再根据声明的顺序依次获得信道的使用权来发送数据。

ADSL的工作原理是将本地回路上可供使用的频谱分成三个频段：_______、上行数据流、下行数据流。

传输层有________和平面结构两种编址方式。

简述移动AdHoc网络的主要特点。

下列操作方式中不属于HDLC扣常用的操作方式的是()

长1km、10Mbit／s的基带总线LAN，信号传输速度为200m／μs，计算一个1000比特的帧从发送开始到接收结束的最大时间是多少?若两相距最远的站点在同一时刻发送数据，则经过多长时间两站发现冲突?

在多种利率并存的条件下起决定作用的利率是___________。

一块土地共100亩，假定每亩的年平均收益为1000元，在年利率为10％的条件下，请计算这块土地的出售价格。

设有线性表A=(a1，a2，…am)，B=(b1，b2，…bn)。试写一合并A、B为线性表C的算法，使得假设A．B均以单链表为存储结构(并且m、n显式保存)。要求C也以单链表为存储结构并利用单链表A、B的结点空间。

细胞内的体液称为()

男，43岁。既往体健，5天前无明确诱因出现发热、恶心、食欲减退伴尿黄，明显乏力。实验室检查：ALT740U／L，TBil74μmol／L。陔患者应考虑的诊断是

下列不是决定普通的工字钢梁抗剪强度的主要因素的是()

（2005年）地面点到（）的铅垂距离称为海拔。

“常在河边走，就是不湿鞋"这句话体现的会计职业道德是()。

粗放型增长的实质是（）。

下列各组社会意识诸形式中，全部属于意识形态范围的是()。

对非领导成员公务员的定期考核采取()方式。