数据结构考研分类复习真题 第六章 答案 (四)[10]

．由于二叉树前序遍历序列和中序遍历序列可唯一确定一棵二叉树因此若入栈序列为…n相当于前序遍历序列是…n出栈序列就是该前序遍历对应的二叉树的中序序列的数目因为中序遍历的实质就是一个结点进栈和出栈的过程二叉树的形态确定了结点进栈和出栈的顺序也就确定了结点的中序序列

下图以入栈序列（解释为二叉树的前序序列）为例说明不同形态的二叉树在中序遍历时栈的状态和访问结点次序的关系

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []