首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个堆栈、若其入栈序列为1,2,3,……,n,不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为n的二叉树的个数,且与不同形态的二叉树一一对应。请简要叙述一种从堆栈输入(固定为1,2,3,……,n)/输出序列对应一种二叉树形态的方
对于一个堆栈、若其入栈序列为1,2,3,……,n,不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为n的二叉树的个数,且与不同形态的二叉树一一对应。请简要叙述一种从堆栈输入(固定为1,2,3,……,n)/输出序列对应一种二叉树形态的方
admin
2018-07-17
44
问题
对于一个堆栈、若其入栈序列为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
学硕统考专业
相关试题推荐
1956年,苏共二十大后,匈牙利大党员和群众强烈要求克服个人崇拜,扩大民主,实行经济改革,一些由知识分子、大学生和干部组成的社团组织纷纷成立,其中最有影响者是()。
16世纪英国国王推行宗教改革的根本目的是()
“我不想变成上帝,或居住在永恒之中,或者把天地抱在怀里,属于人的那种光荣对我就够了。我自己是凡人,我只要求凡人的幸福。”这句话体现的思想是()
世界古代历史上,对东西方文化交流、传播作出突出贡献的是()
绿林军领袖为了大影响,拥立汉宗室()为皇帝,恢复汉的国号,以公元23年为更始元年。
(北魏孝文帝)“初谋南迁,恐众心恋旧,乃示为大举,因以胁定群情,外谋南伐,其实迁也。旧人怀土,多不所愿,内惮南征,无敢言者。于是定都洛阳。”上引材料不能说明的问题是()。
“班禅额尔德尼”最早是由清朝的()皇帝敕封的。
简述按照恩格斯的划分方法人类的起源与进化。
材料一从波罗的海斯德丁(什切青)到亚得里亚海边的里亚斯特,一幅横贯欧洲大陆的铁幕已经降落下来……无一不处在苏联的势力范围之内。
西周的官僚制度已经相当完备,官僚机构庞杂,职官名目繁多。周王室的官僚机构分为两大系统,分别是()。
随机试题
阅读下列材料,回答问题。材料一第聂伯河是俄罗斯欧洲部分的第二大河,欧洲第三大河。河流发源于海拔200~350米的分水岭上。流域北面有白俄罗斯山脊,流域南部是亚速海低地。河流长2200千米,流域面积50.4万平方千米。人们习惯将第聂伯河划分为上
关于租金说法不正确的是()。
诉讼是指建设工程当事人依法请求人民法院行使审判权,审理双方之间发生的纠纷,作出由( )其合法权益,从而解决纠纷的审判活动。
根据事故具体情况,事故调查组成员由有关人民政府、安全生产监督管理部门和负有安全生产监督管理职责的有关部门以及()派人参加。
对于我国商业银行所从事的基金业务,基金监管主体是()
部门差异型通货膨胀形成的关键在于不同部门的劳动生产率高低不同,但劳动者的收入却有趋同的倾向,由此导致了一般物价水平的上涨。
(1)备课(2)成绩(3)新课(4)考试(5)试卷
我国商业银行法第17条:“商业银行的组织形式、组织机构适用《中华人民共和国公司法》的规定。该法律规则属于
下列关于数据库实施、运行和维护的说法中,最恰当的是()。
下列程序的运行结果是()。#include<stdio.h>main(){staticchara[]="Languagef",b[]="programe";char*p1,*p2;intk;
最新回复
(
0
)