Question

画出和下列已知序列对应的树T，并将其转换为相应的二叉树，树的先根

画出和下列已知序列对应的树T，并将其转换为相应的二叉树，树的先根次序访问序列为GFKDAIEBCHJ;树的后根次序访问序列为DIAEKFCJHBG。大神求答案

Answer 1

*以下答案为本人原创，格式有模仿。希望对提主和其他学习数据结构的小伙伴有帮助~

先序：GFKDAIEBCHJ --> G FKDAIEBCHJ
中序：DIAEKFCJHBG --> DIAEKFCJHB G
得出结论：G是树根，G仅有左子树，左子树有FKDAIEBCHJ这些节点，无右子树。

先序：FKDAIEBCHJ --> F KDAIEBCHJ
中序：DIAEKFCJHB --> DIAEK F CJHB
得出结论：F是左子树的根结点，F有左子树DIAEK，右子树CJHB。

(以下讨论F的左子树部分)

先序：KDAIE --> K DAIE
中序：DIAEK --> DIAE K
得出结论：K是左子树F的左根结点，K仅有左子树DIAE，无右子树。

先序：DAIE --> D AIE
中序：DIAE --> D IAE
得出结论：D是左子树K的左根结点，K仅有右子树IAE，无左子树。

先序：AIE --> A IE
中序：IAE --> I A E
得出结论：A是左子树D的右根结点，有左子树I，右子树E。

(以下讨论F的右子树部分)

先序：BCHJ --> B CHJ
中序：CJHB --> CJH B
得出结论：B是左子树F的右根结点，B仅有左子树CHJ，无右子树。

先序：CHJ --> C HJ
中序：CJH --> C JH
得出结论：C是右子树B的左根结点，C仅有右子树HJ，无左子树。

先序：HJ --> H J
中序：JH --> J H
得出结论：H是左子树C的右根结点，H仅有左子树J，无右子树。

还原二叉树为：
G
/
F
/ \
K B
/ /
D C
\ \
A H
/ \ /
I E J