首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个堆栈、若其入栈序列为1,2,3,……,n,不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为n的二叉树的个数,且与不同形态的二叉树一一对应。请简要叙述一种从堆栈输入(固定为1,2,3,……,n)/输出序列对应一种二叉树形态的方
对于一个堆栈、若其入栈序列为1,2,3,……,n,不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为n的二叉树的个数,且与不同形态的二叉树一一对应。请简要叙述一种从堆栈输入(固定为1,2,3,……,n)/输出序列对应一种二叉树形态的方
admin
2018-07-17
62
问题
对于一个堆栈、若其入栈序列为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
学硕统考专业
相关试题推荐
永嘉之乱后,北方的政局是()。①西晋短暂统一的终结②北方长期处于多个政权分立的战乱状态③氐族人建立的前秦和鲜卑人建立的北魏曾统一过北方④民族交往和民族斗争交织在一起⑤民族大融合是历史发展的主流⑥民族大
下列选项中,对东汉度田问题的描述中,不正确的是()
在苏俄新经济政策的内容中,最能体现多种所有制成分的是()。
明代中叶开始,松江地区“合郡男妇,皆以做袜为生,从店中给筹取值”。对此理解错误的是()。
1543年发表解剖学专著《人体结构论》的是()。
下列关于克里斯提尼改革的叙述不正确的是()。
下列对于南海诸岛的名称对应有误的一项是()。
请阅读一首毛泽东诗词:“万木霜天红烂漫,天兵怒气冲霄汉。雾满龙冈千嶂暗,齐声唤,前头捉了张辉瓒。二十万军重入赣,风烟滚滚来天半。唤起工农千百万,同心干,不周山下红旗乱。”这首词是红军哪一次军事斗争的反映()。
若某浮点机基数为4,尾数采用补码表示,则该浮点机的规格化尾数形式为()。
随机试题
国家元首的特征。
关于嵌体洞斜面的预备叙述正确的是
A、第一类医疗器械B、第二类医疗器械C、第三类医疗器械D、特殊用途医疗器械血压计属于
关于淫秽物品的犯罪下列哪些说法是错误的?
桥梁的基本组成包括()。
用友软件中,填制凭证时输入会计科目的方法有()。
设A,B,C均是3阶方阵,满足AB=C,其中则必有()
TheUnitedStatesiswell-knownforitsnetworkofmajorhighwaysdesignedtohelpadrivergetfromoneplacetoanotherinthe
Americanseat______vegetablesperpersontodayastheydidinthe1960s.
DifferentTypesofLearningI.ThedefinitionoflearningA.AprocessofpeopleexperiencingrelationshipbetweeneventsB.【T1】
最新回复
(
0
)