数据遍历问题

来源:百度知道 编辑:UC知道 时间:2024/06/04 14:43:07
先根序列为 ABDEHICFG 中根序列为 DBHIEFGCA 求后根序列为? 我算了好久也没画出二叉树图 希望高手指教下(要求解过程)

****A
***/
**B
*/*\
D**E
**/*\
**H**C
**\*/
**I*F
****\
*****G

.....A
..../
...B
./...\
D.....E
..../...\
...H.....C
....\.../
.....I.F
........\
.........G

过程:首先由先根序列确定根节点为A,查A在中根序列的末位,即左子树为DBHIEFGC,右子树为空;
同理,再确定第二层结点为B,查B在中根序列中的位置可确定,左子树为D(叶子树结束),右子树为HIEFGC;
由右子树确定第三层,结点为E,查E在中根序列中的位置可确定,左子树为HI,右子树为FGC;
则第四层由结点E引出的左子树,结点为H,查H在中根序列中的位置可确定,可确定I在其右,右子树C左边是F,F的右边是G。

则可确定后根序列为DIHGFCEBA。