Question

一道简单的数据结构考试题，学的东西基本都还老师了。。。。那位能不吝赐教，先谢谢了~~

证明：如果一颗二叉树的后序序列为U1,U2.....Un，中序序列为Up1,Up2,....Upn,
则由序列1,2....n可通过一个栈得到序列p1,p2....pn

Answer 1

（1）确定根节点：由后续可知，Un是根节点；在中序中找到Un,可知Un之前的为左子树，之后的为右子树；
（2）分段：用Un将中序序列Up1,Up2,....Upn划分为【左子树中序序列、Un、右子树中续序列】；用得到的左子树序列和右子树序列将后序序列U1,U2.....Un划分为【左子树后续序列、Un、右子树后续序列】
（3）递归划分出新的根节点：用（1）（2）的方法划分左子树（左子树中序序列、左子树后续序列）和右子树（右子树中续序列、右子树后续序列）得到的根节点作为Un的左孩子和右孩子,直到任何一个子树的节点被划分完毕为止

--E
--C
--K
--D
--J
A
--I
--G
--H
--B
--F
print_pre_order : A B F G H I C D J K E
print_in_order : F B H G I A J D K C E
print_post_order : F H I G B J K D E C A

从上面的证明过程可以看出：
（1）知道先序序列和中序序列也可以确定一个树的结构
（2）知道先序序列和后续序列不可以确定一颗树的结构，因为只能确定根，不能确定左右子树。这里列举一个反例：
A
--B
--F
print_pre_order : A B F
print_post_order : F B A
print_in_order : F B A
--F
--B
A
print_pre_order : A B F
print_post_order : F B A
print_in_order : A B F
这个例子中两颗树具有不同的结构，但他们的先序和后续序列却是相同的

追问

问题是证明可以用栈由后序输入得中序输出吧(我是这么理解的)，不是证明怎么由后序和中序得出一颗树(这个我知道。。。)

追答

扯淡吧你？一个序列依赖神容器也得不到另一个序列，不要一拍脑袋就问好不好

追问

我能告诉你这是一道考试题么。。。。