首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个堆栈、若其入栈序列为1,2,3,……,n,不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为n的二叉树的个数,且与不同形态的二叉树一一对应。请简要叙述一种从堆栈输入(固定为1,2,3,……,n)/输出序列对应一种二叉树形态的方
对于一个堆栈、若其入栈序列为1,2,3,……,n,不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为n的二叉树的个数,且与不同形态的二叉树一一对应。请简要叙述一种从堆栈输入(固定为1,2,3,……,n)/输出序列对应一种二叉树形态的方
admin
2018-07-17
61
问题
对于一个堆栈、若其入栈序列为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
学硕统考专业
相关试题推荐
关于希腊古风时代和古典时代的叙述不正确的是()。
东汉末年,朝鲜半岛北部先后兴起()、百济、新罗三个国家。
在苏俄新经济政策的内容中,最能体现多种所有制成分的是()。
关于中世纪西欧城市发展状况,叙述正确的是()。①城市取得自由或自治,一般以赎买为手段。②城市的自由和自治,一般以封建主或国王颁发的特许证书为凭据。③有的城市集体为封君服军役,并履行封臣的其他义务。④城市可视为
杜鲁门总统执政时期,针对美国国内问题提出的计划是()。
对“王与马共天下”的准确理解是()。
明朝中期,邓茂七发动明开国以来最大规模的农民起义,建立政权,他自称()。
材料一从波罗的海斯德丁(什切青)到亚得里亚海边的里亚斯特,一幅横贯欧洲大陆的铁幕已经降落下来……无一不处在苏联的势力范围之内。
年鉴学派开创了总体史研究方法,其代表人物马克·布洛赫研究中世纪的代表作是()
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
随机试题
A.血氨升高B.血清胃泌素升高C.血清淀粉酶升高D.胃酸缺乏E.血清胆红素升高肝性脑病
女,73岁,因不自主震颤8年而就诊,检查肢体远端震颤明显,肌张力增强,肢体活动少,始动困难,面部表情少,瞬目频率慢,行走步态不稳,呈紧迫、细碎、拖地状。老年人此病最常见病因是
采用翻瓣去骨术拔除残根时,切口要求描述哪项是错误的
A.清瘟败毒饮加减B.黄连温胆汤加减C.生脉散合参附汤加减D.参芪地黄汤加减E.六味地黄丸加减急性肾衰竭气脱津伤证的治疗方剂为()
城市房屋拆迁过程中,应当向公证机关办理证据保全的有()。
(2007年卷二第10题)根据知识产权海关保护条例及其实施办法的规定,知识产权权利人向海关总署申请知识产权备案的应当办理下列哪些手续?
下图是“2005年我国东部沿海某市各圈层间人口净迁移模式图”,读图完成下列问题。由图可知,该市()。
在动机理论中,P=D×H×K是()理论。
[*]
•Youwillhearanotherfiverecordings.•Foreachrecording,decidewhatthespeakeristalkingabout.•Writeoneletter(A--
最新回复
(
0
)