证明：如果一棵二叉树的后序序列是,…,中序序列是,…,则由序列1,2,…,n可通过一个栈得到序列,…,.

Question

证明：如果一棵二叉树的后序序列是,…,中序序列是,…,则由序列1,2,…,n可通过一个栈得到序列,…,.

Answer 1

要证明：知道后序与中序,就能得到二叉树?我在学校书上也有,这会
证明：
知道后序后,就可一下找到根结点,就是最后一个结点；
知道根结点,就可以在中序中,从根结点两侧划分出根的左、右子树的中序结点,
再根据根左、右子树的中序结点,从后序中分离出根左、右结点的后序结点,
这样根左、右子树的后、中序都分离出了,再依照刚才的方法再把这两个子树
分别分解,就可以得到所有的结点,用递归算法.