问答题
对于一个堆栈，若其入栈序列为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，(解释为二叉树的前序序列)为例，说明不同形态的二叉树在中序遍历时栈的状态和访问结点次序的关系：
[*]
【答案解析】