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

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

admin2018-07-17  73
问题 对于一个堆栈、若其入栈序列为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://www.kaotiyun.com/show/VfRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)