首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(1)试说明给定一棵二叉树结点的后序序列和中序序列,则此二叉树可构造出来。 (2)一棵二叉树的中序序列为BFDGAEHC,后序序列为FGDBHECA,构造出此二叉树。
(1)试说明给定一棵二叉树结点的后序序列和中序序列,则此二叉树可构造出来。 (2)一棵二叉树的中序序列为BFDGAEHC,后序序列为FGDBHECA,构造出此二叉树。
admin
2009-07-15
70
问题
(1)试说明给定一棵二叉树结点的后序序列和中序序列,则此二叉树可构造出来。
(2)一棵二叉树的中序序列为BFDGAEHC,后序序列为FGDBHECA,构造出此二叉树。
选项
答案
根据二叉树的定义,一棵二叉树通常由一棵左子树和一棵右子树及一个根结点组成,假设二叉树T,它的左子树和右子树分别为T1和T2,已知-X树T的后序序列和中序序列,根据后序序列定义,可知二叉树T的根结点必定为其后序序列的最后一个结点,由此我们得到二叉树T的根结点;而根据中序序列的定义,二叉树T必定具有这样的性质,即其根结点左端的结点序列必为其左子树T1所包含的所有结点的中序序列,根结点右端的结点序列必为其右子树T2所包含的所有结点的中序序列。这样二叉树T左右子树所包含的结点及中序序列也知道了。接下来,我们只要证明二叉树T的左子树T1可构造出来,其右子树T2也可构造出来。同理,对于二叉树T1,已知它的中序序列,从二叉树T的后序序列中也可得出它的后序序列,因此,可得出了I的根结点及T1的左子树T11和右子树T12的中序序列,很明显,就这样一直下去,直到把左子树T1的所有结点分析完,此时必可构造出二叉树T1。同理,右子树T2也可构造出来。因此,知道二叉树T的根结点和它的左右子树,二叉树T也就构造出来了。 [*]
解析
转载请注明原文地址:https://kaotiyun.com/show/1RNZ777K
0
笔试
原NCRE全国计算机四级
NCRE全国计算机四级
相关试题推荐
在Windows操作系统中,采用(65)命令不能显示本机网关地址。
在Linux操作系统中,可以通过修改______文件对DNS搜索顺序及DNS服务器的地址进行配置。
Windows命令行输入()命令后得到下图所示的结果。
如果客户机收到网络上多台DHCP服务器的响应,它将(68)DHCP服务器发送IP地址租用请求。在没有得到DHCP服务器最后确认之前,客户机使用(69)作为源IP地址。(68)
在Windows的cmd命令行窗口中,输入__________________命令将会得到如下图所示的结果。
试题(40)关于虚拟局域网,下面的描述中错误的是()。
有关哈夫曼编码方法,以下说法正确的是(13)。
请写出以下3*3单位矩阵沿顺时针方向旋转90°后所形成的矩阵。如果以下3*3矩阵沿顺时针方向旋转90°后所形成的矩阵就是原来的矩阵:其中,位于*处的元素需要考生填写请完整地写出该矩阵。
请根据C++程序运行时的输出结果,将代码中(1)、(2)空缺处的内容补充完整。指出该代码是否存在内存泄漏。
阅读以下说明和C程序,将填入(n)处的字句在对应栏内。[说明]某旅游服务应用程序运行时,根据输入的两个城市名查找其问的距离。各城市问的距离如表4-1所示。表格中的第一行和第一列表示城市名,表中的每个元素是一个整数,代表该元素所在行和列
随机试题
在电子政务的概念中,核心内容是()
A.inclassB.myteacherC.afterschoolD.arolemodelE.acollegedegreeF.teachingmaterialsOurwho
Thatrockstarhasbecomeaccustomed______receivingmanycompliments.
适用于熔融法制备固体分散物的载体材料是目前国内最常用的包合材料是
下列腹泻的患儿,可选用口服补液盐治疗提
上海市某货物运输自开票纳税人2012年1月1日认定为增值税试点一般纳税人,2012年10月经营情况如下:(1)取得运输业务收入,开具货物运输增值税专用发票1份。注明不含税销售额110万元,增值税税额12.1万元。(2)从事联运业务,从本市某运输企业取得
下列要素中,不属于生产力构成要素的是()。
哈维:血液循环说
设A,B都是可逆矩阵,证明可逆,并求它的逆矩阵。
有一种原则是在整个系统内尽可能引入更多的可变因素,并具有良好的扩展性。该原则称为()。
最新回复
(
0
)