问答题
试问中序序列及后序序列是否能唯一地建立二叉树?若不能，则说明理由；若能，则对中序序列[)BEAFGC和后序序列DEBGFCA构造二叉树。
【正确答案】[证明]
当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＜i＜m时，s，把中序序列分成{S1，S2，…，Si-1}和{Si+1，Si+2，…，Sm}。由于后序遍历是“左子树—右子树—根结点”，所以{P1，P2，…，Pi-1)和{Pi，Pi+1，…Pm-1}是二叉树的左子树和右子树的后序遍历序列。因而由{S1，S2，…，Si-1}和{P1，P2，…，Pi-1}可唯一确定二叉树的左子树，由{S i+1，S i+2，…，Sm}和{Pi，P i+1，…，P m-1}可唯一确定二叉树的右子树。
由中序序列DBEAFGC和后序序列DEBGFCA构造的二叉树如下图：
当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＜i＜m时，s，把中序序列分成{S1，S2，…，Si-1}和{Si+1，Si+2，…，Sm}。由于后序遍历是“左子树—右子树—根结点”，所以{P1，P2，…，Pi-1)和{Pi，Pi+1，…Pm-1}是二叉树的左子树和右子树的后序遍历序列。因而由{S1，S2，…，Si-1}和{P1，P2，…，Pi-1}可唯一确定二叉树的左子树，由{S i+1，S i+2，…，Sm}和{Pi，P i+1，…，P m-1}可唯一确定二叉树的右子树。
由中序序列DBEAFGC和后序序列DEBGFCA构造的二叉树如下图：
【答案解析】