Question

二叉树已知某二叉树的先序序列和中序序列分别？

已知某二叉树的先序序列和中序序列分别
为ABDEFCGHIJK和EFDBCGAJIKH，请画出这
棵二叉树，
并画出二叉树对应的森林。

Answer 1

先序，中序，后序，是按照访问根的先后顺序来定义的。先序是“根左右”，中序是“左根右”，后序是“左右根”。
ABC，如果是先序，A是根，B是左叶，C是右叶;
ABC如果是中序，A是左叶，B是根，C是右叶。
先序序列ABDEFCGHIJK，说明A是这个树的总根;中序EFDBCGAJIKH，说明E是最底层最左边的叶子，(EFDBCG)是左枝，(JIKH)是右枝。据此，我们可以把这个二叉树，第一次分层为:
先序A(BDEFCG)(HIJK)
中序(EFDBCG)A(JIKH)
对于左枝，当作一棵树，用上面的办法，进行第一次分支。
先序BDEFCG，中序EFDBCG，B是总根，EFD是左枝，CG是右支，可以分层:
先序B(DEF)(CG);
中序(EFD)B(CG);
对于右枝，同样分析:
先序HIJK，中序JIKH，H是根，JIK是左枝，没有右枝，分层为:先序H(IJK)()，中序(JIK)H()。空括号表示空枝，这样看得更清楚。
现在，这棵树被分析成:
先序A(B(DEF)(CG))(H(IJK)())，
中序((EFD)B(CG))A((JIK)H())。