已知先序序列：ABCDEFGH,中序序列：CDBAFEHG,画出的二叉树是怎样的?

题目

已知先序序列：ABCDEFGH,中序序列：CDBAFEHG,画出的二叉树是怎样的?

答案

由先序可知,A是根,于是在中序中可知CDB在作,FEHG在右：
A
/
(CDB) (FEHG)
同理,先序划分成A|BCD|EFGH.在左子树BCD中,因先序可得B是根,右子树EFGH中E是根：
A
/
B E
| |
（CD） （FGH）
在B和B的子孙中,由中序序列CDB,可知CD都在B的左子树上.先C后D,可得C是B的左子节点,D是C的右子节点.同理由FGH在中序序列为FEHG可以推出,F在E的左子树上,HG在右子树上：
A
/
B E
/ /
C F (GH）

D
同CD的判断过程,不难得出G是E右子节点,H是G左子节点：
A
/
B E
/ /
C F G
/
D H