由先序序列ABCDEFG,可知,该树的根为A,由中序DCBAEFG可知,A前面的DCB为该树的左子树,A后面的EFG的其右子树。
继续分析,原序列先序被分为两组BCD和EFG,中序分别为DCB和EFG,先序BCD,中序DCB,所以这棵以A为根的树的左子树,其根为B,又因为中序DCB,所以D、C为B节点的左子树,又因为先序BCD,所以C为D的节点,D为C的左子树。
又因为先序EFG,中序EFG,所以这棵以A为根的树的右子树,其根为E,F、G为其右子树,且F为节点,G为右子树。
如下图所示:
满意请采纳,谢谢!
由先序序列ABCDEFG,可知,该树的根为A,由中序DCBAEFG可知,A前面的DCB为该树的左子树,A后面的EFG的其右子树。
继续分析,原序列先序被分为两组BCD和EFG,中序分别为DCB和EFG,先序BCD,中序DCB,所以这棵以A为根的树的左子树,其根为B,又因为中序DCB,所以D、C为B节点的左子树,又因为先序BCD,所以C为D的节点,D为C的左子树。
又因为先序EFG,中序EFG,所以这棵以A为根的树的右子树,其根为E,F、G为其右子树,且F为节点,G为右子树。
如下图所示:
A
/ \
B E
/ \
C F
/ \
D G
满意请采纳,谢谢!