由二叉树的中序序列及前序序列能唯一地建立二叉树 试问中序序列及后序序列是否也能唯一地建立二
序列,明理,正确答案
已帮助 人
由二叉树的中序序列及前序序列能唯一地建立二叉树，试问中序序列及后序序列是否也能唯一地建立二叉树，不能，则说明理由，若能，对中序序列DBEAFGC和后序序列DEBGFCA构造二叉树。【南京理工大学1998四(3分)】
请帮忙给出正确答案和分析，谢谢！
-
正确答案：在已经说明由二叉树的前序序列和中序序列可以唯一确定一棵二叉树现在来证明由二叉树的中序序列和后序序列也可以唯一确定一棵二叉树。当n=1时只有一个根结点由中序序列和后序序列可以确定这棵二叉树。设当n=m一1时结论成立现证明当n=m时结论成立。设中序序列为S1S2…Sm后序序列是P1P2…Pm。因后序序列最后一个元素Pm是根则在中序序列中可找到与Pm相等的结点(设二叉树中各结点互不相同)Si(1≤i≤m)因中序序列是由中序遍历而得Si是根结点S1S2…Si一1是左子树的中序
在已经说明由二叉树的前序序列和中序序列可以唯一确定一棵二叉树,现在来证明由二叉树的中序序列和后序序列,也可以唯一确定一棵二叉树。当n=1时,只有一个根结点,由中序序列和后序序列可以确定这棵二叉树。设当n=m一1时结论成立,现证明当n=m时结论成立。设中序序列为S1,S2,…,Sm,后序序列是P1,P2,…,Pm。因后序序列最后一个元素Pm是根,则在中序序列中可找到与Pm相等的结点(设二叉树中各结点互不相同)Si(1≤i≤m),因中序序列是由中序遍历而得,Si是根结点,S1,S2,…,Si一1是左子树的中序