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

admin2010-04-24 60

问题已知一棵二叉树的前序遍历序列是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。请画出相应的二叉树，并求出对应此二叉树的后序遍历序列，此二叉树是完全二叉树吗?完全二叉树有什么性质(特点)?

数据结构

理工类

计算机网络中，分层和协议的集合称为计算机网络的体系结构。目前应用最广泛的是()

开放最短路径优先协议(OSPF)采用的路由算法是()

IPV6将IP地址的长度增加到了_______，使地址空间增大了296倍。

简要说明协议的基本含义以及其三要素的含义与关系。

试述目前我国主要采用的货币政策的中介指标与操作指标。

中国人民银行发行第一套人民币的时间是()

设有指针head指向不带表头结点的单链表，用next表示结点的一个链域，指针p指向与链表中结点同类型的一个新结点。现要将指针p指向的结点插入表中，使之成为第一个结点，则所需的操作为“p→next=head；”和“_______”。

若一个二叉树的叶子是某子树的中序遍历序列中的最后一个结点，则它必是该子树的_________序列中的最后一个结点。

正常新生儿出生24h护理不妥的是

下列哪种义务属于主给付义务：()

招标采购法律法规体系包括两个方面，一是招标采购专业法律规范，二是相关法律规范。下列选项属于招标采购专业法律规范的是()。

OutlookExpress是用来浏览网页的软件。()

下列说法正确的是()。

在金融期货交易和金融期权交易中，交易双方都必须开立保证金账户。()

下列有关前沿科技的应用及评价，表述不正确的是：

【西安事变】西北大学2013年中国史真题；浙江工商大学2016年专门史真题；苏州科技大学2017年中国通史真题