首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个堆栈、若其入栈序列为1,2,3,……,n,不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为n的二叉树的个数,且与不同形态的二叉树一一对应。请简要叙述一种从堆栈输入(固定为1,2,3,……,n)/输出序列对应一种二叉树形态的方
对于一个堆栈、若其入栈序列为1,2,3,……,n,不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为n的二叉树的个数,且与不同形态的二叉树一一对应。请简要叙述一种从堆栈输入(固定为1,2,3,……,n)/输出序列对应一种二叉树形态的方
admin
2018-07-17
69
问题
对于一个堆栈、若其入栈序列为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
学硕统考专业
相关试题推荐
最早以立法形式巩固大化改新成果的法令是()。
“我不想变成上帝,或居住在永恒之中,或者把天地抱在怀里,属于人的那种光荣对我就够了。我自己是凡人,我只要求凡人的幸福。”这句话体现的思想是()
巴黎和会上,英美主张把原德国在山东的权利转让给日本,华盛顿会议又表示支持中国让日本归还山东的要求,英美态度发生变化的根本原因是()。
下列内容,哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展,在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张,从经济上瓜分世界
利玛窦与徐光启合作翻译的(),介绍了曾经流行于欧洲的欧几里得平面几何的系统理论,大大地丰富了中国古代几何学的内容。
《洛迦诺公约》给人留下了深刻的印象,张伯伦认为《公约》“标志着和平年代和战争年代真正的分界线。”对此理解最为准确的一项是()。
1940年毛泽东的《新民主主义论》:“而所谓民主主义,现在已不是旧范畴的民主主义,已不是日民主主义,而是新范畴的民主主义,而是新民主主义”。毛泽东分民主革命的两个阶段主要依据是
加尔文教传播到法国后,其信仰者被称为()。
一个由高速缓冲存储器Cache与主存储器组成的二级存储系统。已知主存容量为1MB,按字节编址,缓存容量为32KB,采用组相联方式进行地址映射与变换,主存与缓存的每一块为64B,缓存共分8组。(1)写出主存与缓存的地址格式(标明各字段名称与位数)
随机试题
肺炎并发呼吸衰竭的主要诊断依据为
以下不属于物流信息系统分析主要内容的是()
男性,44岁。右小腿被车撞伤1天,剧痛。右足不能主动背伸,足背动脉搏动消失,足趾感觉过敏,小腿肿,皮肤略红,温度稍高。此症的严重后果是
直接对抗由于强心苷中毒引起心动过缓的药物为
短管骨骨干结核的好发部位是()。
下列仪表管道的弯曲半径,错误的是()。
美国某投资公司购买了“百度”在NASDAQ上市的股票,则记在中国()
著有奠定了中医治疗学基础的《伤寒杂病论》的医学家是()。
有5个正方形如下图叠放。已知每个正方形的边长都是5cm,它们所覆盖住的面积为115cm2。则阴影部分的面积为()cm2。
Completethenotesbelow.WriteNOMORETHANTWOWORDSforeachanswer.TheArgussystemDevelopedbyRo
最新回复
(
0
)