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

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

先序,中序,后序,是按照访问根的先后顺序来定义的。先序是“根左右”,中序是“左根右”,后序是“左右根”。
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())。
温馨提示:答案为网友推荐,仅供参考