设一棵二叉树的中序遍历序列为: C E I F G B A D H , 后序遍历序列为: E I C B G A H D F 求: (1)画出这棵二叉树。 (2)写出该二叉树的前序遍历序列。 (3)将这棵二叉树转换成对应的树(或森林)。
时间: 2023-06-19 21:05:51 浏览: 75
(1) 根据中序遍历序列和后序遍历序列可知根节点为F,因为后序遍历的最后一个元素为根节点,F在中序遍历中左侧的为左子树,右侧的为右子树;以此类推,递归构建整棵树,如下图所示:
```
F
/ \
C B
/ \ / \
E I G A
/ \
H D
```
(2) 该二叉树的前序遍历序列为:F C E I B G A H D
(3) 将该二叉树转换成对应的树(或森林)如下图所示:
```
F B
/ \ / \
C D G A
/ \ / \ \
E I H F D
\
B
/ \
G A
/
H
```
相关问题
设某二叉树的前序遍历序列为:ABCDEFGHI,中序遍历序列为:BCAEDGHFI,则二叉树的后序序列为
根据二叉树遍历的性质,可以得到以下信息:
- 前序遍历的第一个节点为根节点,即A为根节点。
- 中序遍历中,A将树分成了左右两个子树,左子树为BCAE,右子树为GHFI。
- 同样地,前序遍历中,A之后的三个节点BCD为左子树的前序遍历序列,EFGHI为右子树的前序遍历序列。
根据这些信息,可以递归地构建二叉树并求出后序遍历序列:
1. 对于左子树,前序遍历序列为BCD,中序遍历序列为BCAE,递归构建左子树并求出后序遍历序列CDABE。
2. 对于右子树,前序遍历序列为EFGHI,中序遍历序列为GHFI,递归构建右子树并求出后序遍历序列GIFHE。
3. 将左右子树的后序遍历序列拼接到根节点后面,得到后序遍历序列CDABEGIFHEA。
因此,该二叉树的后序遍历序列为CDABEGIFHEA。
设一棵二叉树的后序序列为:D G E B H F C A中序遍历序列为:D B G E A C H F (1)画出这棵二叉树。 (2)写出该二叉树的先序、中序、后序遍历序列。 比较你写的后序和中序序列与题目的是否一致。
(1) 二叉树如下图所示:
```
A
/ \
B C
/ \ / \
D E H F
/
G
```
(2) 该二叉树的先序遍历序列为:A B D E G C H F,中序遍历序列为:D B G E A C H F,后序遍历序列为:D G E B H F C A。
题目中给出的后序遍历序列和中序遍历序列与我计算得到的一致。