根据先序和中序序列求二叉树
根据先序和中序序列求二叉树
$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