Question

数据结构二叉树已知中序遍历，后序遍历，求先序遍历？？？

都知道已知先序遍历，中序遍历得后序遍历好得。。。但已知中序遍历，后序遍历，求先序遍历该怎么考虑呢？如果是个选择还好做,但要是填空该怎么考虑？？请举例说明！！非常感谢

Answer 1

通过分段来解决,找到根节点(通过后序),然后将中序序列分成两段，左右子树，然后递归进行，分的时候可以利用求中序的左右子树的结点个数来确定后序序列的每段节点个数.
例如中 BDACE
后 DBECA1.由后序遍历的知道最后一个节点一定是根节点,该例中为A
2.中序中对应的根就是A,推得A为根BD为左子树CE为右子树
3.左子树2个结点右子树也为2个,因为后序遍历是先左再右因此将后序分为两段左DB,右EC
4.由此确定左子树的根为B,右子树根为C
5.在回到中序中左子树部分 BD (B为根)其右子树为D 左子树部分 根为C右子树为E
如果结点和多的时候判断都是这样递归地进行.
由上述推得的结果
得到2叉树的结构图
-----A
----/--\
---B---C
----\-----\
-----D----E
得前序为 ABCDE