首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个堆栈、若其入栈序列为1,2,3,……,n,不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为n的二叉树的个数,且与不同形态的二叉树一一对应。请简要叙述一种从堆栈输入(固定为1,2,3,……,n)/输出序列对应一种二叉树形态的方
对于一个堆栈、若其入栈序列为1,2,3,……,n,不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为n的二叉树的个数,且与不同形态的二叉树一一对应。请简要叙述一种从堆栈输入(固定为1,2,3,……,n)/输出序列对应一种二叉树形态的方
admin
2018-07-17
59
问题
对于一个堆栈、若其入栈序列为1,2,3,……,n,不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为n的二叉树的个数,且与不同形态的二叉树一一对应。请简要叙述一种从堆栈输入(固定为1,2,3,……,n)/输出序列对应一种二叉树形态的方法,并以入栈序列1,2,3(即n=3)为例加以说明。
选项
答案
由于二叉树前序遍历序列和中序遍历序列可唯一确定一棵二叉树。因此,若入栈序列为1,2,3,……,n相当于前序遍历序列是1,2,3,……n,出栈序列就是该前序遍历对应的二叉树的中序序列的数目,而中序遍历的过程实质就是一个结点进栈和出栈的过程。 二叉树的形态确定了结点进栈和出栈的顺序,也就确定了结点的中序序列。当结点入栈序列为{1,2,3}时,出栈序列可能为:{3,2,1},{2,3,1},{2,1,3},{1,3,2},{1,2,3},它们对应二叉树如下: [*] 【扩展】进栈出栈操作与二叉树中序遍历的关系:①一个结点进栈后有两种处理方式:要么立刻出栈(没有左孩子):或者下一个结点进栈(有左孩子)。②一个结点出栈后也有两种处理方式:要么继续出栈(没有右孩子);或者下一个结点进栈(有右孩子)。
解析
转载请注明原文地址:https://kaotiyun.com/show/VfRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
最晚到汉武帝时期,出现了我国第一部算学著作(),它记载了用竿标测日影以求日高的方法,从而认识了勾股定理。
洋务派创办军事工业的方式是()。
元朝在中央设置中书省、地方则设置行中书省,其目的是()。
改革开放以后,我国农村产业结构巨大的转变表现在()。
“二战”爆发的原因是多种因素综合作用的结果,其中最根本的因素是()。
火的使用,是人类在征服自然的进程中所取得的伟大成果。人类开始使用天然火是在()。
印度列国时代出现了16个国家,其中大部分是王国,只有少数的共和国。下列属于共和国的是()。
电子计算机的发展经过了四代,①电子数值积分计算机(ENIAC);②集成电路计算机;③大规模集成电路计算机;④晶体管计算机;⑤人工智能计算机,其先后顺序是()。
某计算机字长16位,采用16位定长指令字结构,部分数据通路结构如下图所示。图中所有控制信号为1时表示有效、为0时表示无效。例如控制信号MDRinE为1表示允许数据从DB打入MDR,MDRin为1表示允许数据从内总线打入MDR。假设MAR的输出一直处于使能状
对于下图G,按下列条件试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。(1)假定它们均采用邻接矩阵表示;(2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链
随机试题
患者,女,34岁。诊断哮喘5年。长期应用倍氯米松(必可酮)气雾剂治疗,250μg/d,症状控制满意。近来受凉后再次出现喘憋,活动耐力无明显受限,夜间偶有发作。发作时吸入沙丁胺醇症状可缓解。患者治疗后出现口腔黏膜白色斑点,不正确的治疗措施是
前列腺癌最常见的组织学类型是
肛瘘
患者,女,14岁。左面部肿大,畸形,随年龄而增长。检查:左鼻及唇颊增大、下坠,软,面部及躯干皮肤有多处棕色斑。最可能的临床诊断是
A.风湿性心脏病B.心律失常C.二尖瓣狭窄伴关闭不全D.心功能Ⅲ级E.贫血于病因诊断的是()
某教学楼由10层和2层两部分组成,均拟设埋深相同的1层地下室。地基土为均匀的细粒土,场地在勘察深度内未见地下水。以下基础方案中的()不能有效减少高低层的不均匀沉降。
法律意义上的物是指_________的生产资料和消费资料。()
以下属于自物权的是( )。
下面不属于需求分析阶段任务的是
Manyoftheemployeesthinktheircareerpathbeginsduringtheiremploymentorwhentheygetajob.Butbasically,ifwelooka
最新回复
(
0
)