首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(1)试说明给定一棵二叉树结点的后序序列和中序序列,则此二叉树可构造出来。 (2)一棵二叉树的中序序列为BFDGAEHC,后序序列为FGDBHECA,构造出此二叉树。
(1)试说明给定一棵二叉树结点的后序序列和中序序列,则此二叉树可构造出来。 (2)一棵二叉树的中序序列为BFDGAEHC,后序序列为FGDBHECA,构造出此二叉树。
admin
2009-07-15
105
问题
(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全国计算机四级
相关试题推荐
(50)不属于防火墙能够实现的功能。
以下关于文件index.htm的叙述中,正确的是()。
操作系统文件管理中,目录文件是由________组成的。
按照VLAN中继协议的规定,交换机运行在__________________模式时可以进行VLAN配置,但是配置信息不会传播到其他交换机。
在Windows操作系统中,_________组件的作用是在本地存储DNS查询信息。
EIA/TIA 568B标准的RJ45接口线序如下图所示,3、4、5、6四个引脚的颜色分别为(40)。
阅读以下说明和C程序,将填入(n)处的字句在对应栏内。[说明]某旅游服务应用程序运行时,根据输入的两个城市名查找其问的距离。各城市问的距离如表4-1所示。表格中的第一行和第一列表示城市名,表中的每个元素是一个整数,代表该元素所在行和列
以下是交换机Switch1的部分配置。请解释配置命令。1.配置VLANTrunk端口……Switch1(config)#interfacef0/24(进入端口24配置模式)Switch1(config-if)#swi
In C program, all variables must be(70)before use, usually at the beginning of the function before any(71)statements.
Inatreedirectoryofafilesystem,relativepathnamecanbeusedtofindfilesforimprovingdirectoryretrieval.Todothis,
随机试题
症见突然昏仆,不省人事,口眼歪斜,牙关紧闭,肢体强劲而不温,面白唇黯,喉中痰声,静卧不烦,苔白腻,脉沉滑,其治疗宜选用
关于血型检测室内质控错误的认识是
后牙修复体颊舌面突度过小会引起
对用于路面施工的颗粒材料,有级配要求的路面结构层有()。
如下图所示参数,10kV配电装置室内最高环境温度为+30℃,三相母线水平布置,导体平放。10.5kV主母线持续工作电流为()。
儿童之间绝大多数的社会性交往是在()中发生的。
品德是个体的先天禀赋。()
CD存款工具的出现是为了规避利率风险。()(中央财经大学2013真题)
在一次聚会上,10个吃了水果色拉的人中,有5个很快出现了明显的不适。吃剩的色拉立刻被送去检验。检验的结果不能肯定其中存在超标的有害细菌。因此,食用水果色拉不是造成食用者不适的原因。如果上述检验结果是可信的,则以下哪项对上述论证的评价最为恰当?
HowmanyLondonundergroundlinesarethere?Onwhichformsoftransportcanaone-dayTravelcardbeused?
最新回复
(
0
)