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

．（）

（）设二叉树的前序遍历序列为PP…Pm中序遍历序列为SS…Sm因为前序遍历是根左右中序遍历是左根右则前序遍历序列中第一个结点是根结点（P）到中序序列中查询到Si=P根据中序遍历时根结点将中序序列分成两部分的原则有

若i=即S=P则这时的二叉树没有左子树; 否则SS…Si是左子树的中序遍历序列用该序列和前序序列PP…Pi去构造该二叉树的左子树

若i=m即Sm=P则这时的二叉树没有右子树; 否则Si+Si+…Sm是右子树的中序遍历序列用该序列和前序序列中Pi+Pi+…Pm去构造该二叉树的右子树算法描述请参见下面算法设计第题

（）若前序序列是abcd并非由这四个字母的任意组合（!=）都能构造出二叉树因为以abcd为输入序列通过栈只能得到/(n+)*n!/(n!*n!)= 种即以abcd为前序序列的二叉树的数目是任取以abcd作为中序遍历序列并不全能与前序的abcd序列构成二叉树例如若取中序列dcab就不能

该棵二叉树的形态及中序序列略

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