已知一棵二叉树的后序遍历序列为EICBGAHDF,中序遍历序列为CEIFGBADH,画出该二叉树
时间: 2023-06-23 21:55:07 浏览: 125
二叉树的结构如下所示:
```
H
/ \
D F
/ \ / \
I C E G
/ / \
B A I
```
解析:
根据后序遍历序列,最后一个元素为根节点,即根节点为F;
根据中序遍历序列,F在序列的第5个位置,因此F的左子树为CEIG,右子树为ADH;
由此,可以将问题拆分为两个子问题,分别求CEIG和ADH的二叉树结构。
对于CEIG,它的根节点为E,E的左子树为空,右子树为CIG。由于CIG的后序遍历序列为CIG,中序遍历序列为CIG,因此可以得到CIG的二叉树结构:
```
I
/ \
C G
```
对于ADH,它的根节点为H,H的左子树为AD,右子树为空。由于AD的后序遍历序列为IDAC,中序遍历序列为CEIFGB,可以得到AD的二叉树结构:
```
D
/ \
I C
```
综上,可以得到完整的二叉树结构。
相关问题
已知二叉树的先序遍历序列为 DAGICJBFHE 中序遍历序列为 GACIDFBHJE 则后序遍历序列为
根据二叉树的遍历序列重构二叉树,得到的二叉树如下所示:
```
D
/ \
A I
/ / \
G C J
/ \
B F
/ \
H E
```
根据后序遍历的定义,后序遍历的最后一个节点为根节点。因此,我们可以先确定根节点为 E。然后,我们可以根据中序遍历确定左子树和右子树的节点集合。具体地,E 的左侧为左子树的节点集合 {G, A, C, I, D, F, B, H},右侧为右子树的节点集合 {J}。接下来,我们可以根据左子树和右子树的节点集合递归地确定左子树和右子树的后序遍历序列。
左子树的后序遍历序列为 {G, A, C, I, F, H, B, J, E, D},右子树的后序遍历序列为 {J}。因此,二叉树的后序遍历序列为 {G, A, C, I, F, H, B, J, E, D, J}。
因此,答案为:GACIDFBHJJEED。
已知二叉树中序遍历序列为CBDFEGAMLNKJOPRQIHS, 后序遍历序列为CFGEDBMNLKRQPOJISHA,试画出此二叉树
根据二叉树遍历的特点,可以确定该二叉树的根节点为序列中的最后一个节点 "A"。然后在中序遍历中找到根节点的位置,根节点左边的序列为左子树的中序遍历序列,右边的序列为右子树的中序遍历序列。同样,在后序遍历中,根节点左边的序列为左子树的后序遍历序列,右边的序列为右子树的后序遍历序列。然后递归构造左右子树即可。
构造过程如下:
1. 根据中序遍历序列,确定根节点为 "A",并找到 "A" 在中序遍历序列中的位置。
2. 根据后序遍历序列,确定根节点为 "A",并找到 "A" 在后序遍历序列中的位置。
3. 根据中序遍历序列和后序遍历序列,确定左子树的中序遍历序列为 "CBDFEGM",左子树的后序遍历序列为 "CFGEDBM"。
4. 根据中序遍历序列和后序遍历序列,确定右子树的中序遍历序列为 "LNKJOPRQIHS",右子树的后序遍历序列为 "NLKRQPOJISH".
5. 递归构造左右子树,得到完整的二叉树。
最终的二叉树如下图所示:
```
A
/ \
/ \
/ \
/ \
C L
/ \ / \
/ \ / \
B D K N
/ \ / \
/ \ / \
F E J O
/ \ \
/ \ \
G M I
\
\
S
```
其中,节点的左子树在上方,右子树在下方。