首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个堆栈、若其入栈序列为1,2,3,……,n,不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为n的二叉树的个数,且与不同形态的二叉树一一对应。请简要叙述一种从堆栈输入(固定为1,2,3,……,n)/输出序列对应一种二叉树形态的方
对于一个堆栈、若其入栈序列为1,2,3,……,n,不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为n的二叉树的个数,且与不同形态的二叉树一一对应。请简要叙述一种从堆栈输入(固定为1,2,3,……,n)/输出序列对应一种二叉树形态的方
admin
2018-07-17
23
问题
对于一个堆栈、若其入栈序列为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
学硕统考专业
相关试题推荐
西欧早期资产阶级反封建斗争以反天主教会的方式进行,主要原因是()①天主教会是最有势力的封建主集团②天主教会是封建的精神工具③天主教会日益腐败④近代自然科学的兴起
下列城市:①南京②厦门③天津④杭州,按其在近代历史上开放为商埠的时间先后顺序排列应该是()
唐朝官营手工业中,每年服役二十天,在政府“趋役不尽及别有和雇”的情况下,可“纳资代役”的是()。
武昌起义后,全国革命形势发展的同时也潜伏着失败的危机,这主要是由于()。
解放军渡江战役中横渡长江的东西两个攻击点是()。
某32位机(机器字长32位)的一台外设通过32位总线与系统内存相连。CPU每秒执行100条指令,平均每条指令需要5个机器周期,其中3个周期必须访问内存,内存读写需一个机器周期,假定CPU在95%的时间内持续执行“背景程序”,且这段时间内不执行I/O指令。现
某计算机采用微程序控制方式,微指令字长32位,采用字段直接编码的控制方式,共有55个微命令,可分为6个互斥组,分别包含1、3、7、8、12、24个微命令。另外,该机共有5个可判定的外部条件,采用断定方式形成后续微指令地址。(1)设计该机微指令的格式,
高度为7的AVL树最少有()个结点。
已知有6个顶点(顶点编号为0~5)的有向带权图G,其邻接矩阵A为上三角矩阵,按行为主序(行优先)保存在如下的一维数组中。要求:画出有向带权图G。
网络中的广播信息太多时能使整个网络性能急剧恶化,这种现象称为()。
随机试题
白头翁汤的功用是
骨折3天应该进行的康复训练
男,77岁,饮酒后呕咖啡样物1次,量约150ml,3个月来因冠心病口服小剂量阿司匹林。查体:P80次/分,BP128/68mmHg,神清,腹软,剑突下轻压痛,未触及包块,肝脾肋下未触及。首选的检查是
最常见的女性生殖器结核是
某甲自己办了一家私营建筑公司。为争得某市一项大型工程的承包权,某甲与其他建筑公司串通在投标时都尽量压价,结果某甲中标;某甲为服务作虚假宣传,情节严重,并捏造,散布虚假事实,使该市一国有建筑公司未中标,商业信誉受损并造成重大损失。在建设过程中,某甲又使用虚假
某土石坝工程项目法人与施工单位签订了工程施工合同,合同中估算工程量为8000m3,单价为200元/m3,合同工期为6个月,有关付款条款如下:(1)开工前项目法人应向施工单位支付合同总价20%的工程预付款。(2)项目法人自第一个月起,从施
根据《个人所得税法》的规定,工资、薪金的应纳税所得额以每月收入额减除( )后的余额。
建设工程项目总进度目标的控制是()项目管理的任务。
党员违法犯罪后受到国法追究,可不再受党纪追究。()
WriteonyourANSWERSHEETONEacompositionofabout200wordsonthefollowingtopic:Themoderneraissaidtobemarkedbyr
最新回复
(
0
)