二叉树

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

(2)由二叉树的中序序列和后序序列,也可以唯一确定一棵二叉树。证明如下:

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

设当n=m-1时结论成立,现证明当n=m时结论成立。

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

若i=1,则S1是根,这时二叉树的左子树为空,右子树的结点数是m-1,则{S2,S3,…,Sm}和{P1,P2,…,Pm-1}可以唯一确定右子树,从而也确定了二叉树。

若i=m,则Sm是根,这时二叉树的右子树为空,左子树的结点数是m-1,则{S1,S2,…,Sm-1}和{P1,P2,…,Pm-1}唯一确定左子树,从而也确定了二叉树。

最后,当1

可唯一确定二叉树的左子树,由{Si+1,Si+2,…,Sm}和{Pi,Pi+1,…,Pm-1}可唯一确定二叉树的右子树 。

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