已知：先序：ABDGEHCFIJ。中序：GDBEHACIFJ，构造二叉树。

coolisen · 2018-4-30 01:12:59

由先序可知改树根为A
由中序序列可知该树左子树包含节点个GDBEH，右子树包含CIFJ
继续刚才的方法，在GDBEH中，根据先序ABDGEH聽聽CFIJ聽聽,可知左子树根节点为B，右子树为C，中序GD聽聽聽聽B聽聽聽聽EH聽聽聽A聽聽聽聽C聽聽聽聽IFJ，即：GD为B的左子树，EH为右子树，C的左子树没有，IFJ为其右子树。
先序A聽聽B聽聽DG聽聽聽EH聽聽C聽聽聽FIJ聽聽，DG两个节点D为根，EH中E为根，在中序G聽D聽*聽聽聽B聽聽聽聽*EH聽聽聽A聽聽聽聽C聽聽聽聽IFJ中G在D前面，说明是左子树，同理H为E的右子树。
同理可知以C为根节点的树左子树空，右子树根为F，F的左右子树分别为I和J。
树搞定，后续序列为GDHEBIJFCA.。

已知：先序：ABDGEHCFIJ。中序：GDBEHACIFJ，构造二叉树。

1 个回复

浏览过的版块