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

．给定二叉树结点的前序序列和对称序（中序）序列可以唯一确定该二叉树因为前序序列的第一个元素是根结点该元素将二叉树中序序列分成两部分左边（设l个元素）表示左子树若左边无元素则说明左子树为空右边（设r个元素）是右子树若为空则右子树为空根据前序遍历中根?左子树右子树的顺序则由从第二元素开始的l个结点序列和中序序列根左边的l个结点序列构造左子树由前序序列最后r个元素序列与中序序列根右边的r个元素序列构造右子树

由二叉树的前序序列和后序序列不能唯一确定一棵二叉树因无法确定左右子树两部分例如任何结点只有左子树的二叉树和任何结点只有右子树的二叉树其前序序列相同后序序列相同但却是两棵不同的二叉树

．前序遍历是根左右中序遍历是左根右后序遍历是左右根三种遍历中只是访问根结点的时机不同对左右子树均是按左右顺序来遍历的因此所有叶子都按相同的相对位置出现

．在第题已经说明由二叉树的前序序列和中序序列可以确定一棵二叉树现在来证明由二叉树的中序序列和后序序列也可以唯一确定一棵二叉树

当n=时只有一个根结点由中序序列和后序序列可以确定这棵二叉树

设当n=m时结论成立现证明当n=m时结论成立

设中序序列为SS…Sm后序序列是PP…Pm因后序序列最后一个元素Pm是根则在中序序列中可找到与Pm相等的结点（设二叉树中各结点互不相同）Si(≤i≤m)因中序序列是由中序遍历而得所以Si是根结点SS…Si是左子树的中序序列而Si+Si+…Sm是右子树的中序序列

若i=则S是根这时二叉树的左子树为空右子树的结点数是m则{SS…Sm}和{PP…Pm}可以唯一确定右子树从而也确定了二叉树

若i=m则Sm是根这时二叉树的右子树为空左子树的结点数是m则{SS…Sm}和{PP…Pm}唯一确定左子树从而也确定了二叉树

最后当<i<m时Si把中序序列分成{SS…Si}和{Si+Si+…Sm}由于后序遍历是左子树右子树根结点所以{PP…Pi}和{PiPi+…Pm}是二叉树的左子树和右子树的后序遍历序列因而由{SS…Si}和{PP…Pi}

可唯一确定二叉树的左子树由{Si+Si+…Sm}和

{PiPi+…Pm}可唯一确定二叉树的右子树

由中序序列DBEAFGC和后序序列DEBGFCA构

造的二叉树如图

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