对于一个堆栈、若其入栈序列为1，2,3，……，n，不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为n的二叉树的个数，且与不同形态的二叉树一一对应。请简要叙述一种从堆栈输入(固定为1，2,3，……，n)／输出序列对应一种二叉树形态的方

admin2018-07-17 39

问题对于一个堆栈、若其入栈序列为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题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

30年代，美国推行“中立”政策之所以对法西斯侵略起了绥靖作用，主要是因为它()。

一战后，英国拒绝加入法国的安全保障体系，其原因是()。

春秋时期的鲁国初税亩和战国时期以商鞅变法为代表的各国变法，在历史上产生了深刻的影响。这些变法的最大作用和产生的最主要的社会后果是()。

中共中央通过《关于建国以来党的若干历史问题的决议》的会议是()。

武昌起义所使用的旗帜是()。

主张“知己知彼，百战不殆”、“势者因利而制权也”的是()。

张女士，消化道溃疡久治不愈，今突然呕血约700ml，立即给予输血，10min后病人主诉头痛、发热、四肢麻木、腰背部剧痛伴胸闷、气促。护士应首先考虑该病人发生了

按有关规定，下列采购方式中，可以进行多次报价竞争的采购方式是（）。

下列关于洛伦兹循环说法错误的是()。

下列关于采用成本模式进行后续计量的投资性房地产改扩建后仍作为投资性房地产的说法中，正确的有()。

物业服务合同应具备的内容为()。

智力游戏是学前儿童最喜欢的创造性游戏。()

课堂教学中，经常出现教师在学生不注意参与学习时突然加重语气或提高声调的现象，教师采用这种手段的目的是为了引起学生的()。

关于香港特别行政区行政长官，以下说法错误的是()。

设f(x)存[0，1]上连续，在(0，1)内可导，f(0)=0，f(1/2)=1，f(1)=0．证明：(1)存在η∈(1/2，1)，使得f(η)=η；(2)对任意的k∈(-∞，+∞)，存在ξ∈(0，η)，使得f′(ξ)-k[f(ξ)-ξ]=1．