根据先序和中序序列求二叉树
根据先序和中序序列求二叉树
$1、题目
已知一棵二叉树的先序遍历序列和中序遍历序列分别为ABDGHCEFI和GDHBAECIF，请画出这棵二叉树，然后给出该树的后序遍历序列。
- 先序遍历：ABDGHCEFI
- 中序遍历：GDHBAECIF
$2、分析
由前序和后序分析子树
- 由先序：
A|BDGHCEFI - 由中序：
GDHB|A|ECIF - 知：
A 为根节点，A 左子树为GDHB ，右子树为ECIF
- 由先序：
BDGH−>B|DGH - 由中序：
GDHB−>GDH|B - 知：
B 有左子树，无右子树，左子树为GDH
- 由先序：
DGH−>D|GH - 由中序：
GDH−>G|D|H - 知：
D 有左子树：G ，右子树：H 如图：
- 由上可得，
A 的左子树：
- 由先序：
CEFI−>C|EFI - 由中序：
ECIF−>E|C|IF - 知：
C 有左子树，为：E ，有右子树：IF
- 由先序：
FI−>F|I - 由中序：
IF−>I|F