设一棵二叉树的先序序列: A B D F C E G H ,中序序列: B F D A G E H C ①画出这棵二叉树。 ②画出这棵二叉树的后序线索树。 ③将这棵二叉树转换成对应的树(或森林)。
时间: 2024-03-12 22:45:12 浏览: 45
好的,我来回答你的问题:
① 画出的二叉树如下所示:
```
A
/ \
B C
/ \ /
D F E
\ \
G H
```
② 画出的后序线索树如下所示:
```
D
\
F
\
B
\
G
\
H
\
E
\
C
\
A
```
③ 将二叉树转换成对应的树(或森林)有多种方式,下面给出一种可能的转换方式:
```
A
/ | \
B C E
/ \ \
D F H
\
G
```
这里将原二叉树转换成了一个根节点为 A,三个子树分别为 B-D-F、C-E 和 G-H 的树。
相关问题
设一棵二叉树的先序序列: a b d f c e g h ,中序序列: b f d a g e h c
这棵二叉树的结构如下:
```
a
/ \
b c
/ \ / \
d f e g
\
h
```
其中,根节点为 a,左子树为 b d f,右子树为 c e g h。
设一棵二叉树的先序序列: A B D F C E G H ,中序序列: B F D A G E H C 求它的后序序列
根据先序序列的第一个节点 A,可以确定该二叉树的根节点为 A。然后在中序序列中找到 A 的位置,将中序序列分成左右两个子序列:
左子序列:B F D
右子序列:G E H C
接下来对左右子序列分别递归进行同样的操作,直到序列中只剩下一个节点。具体过程如下:
左子树的先序序列:B D F
左子树的中序序列:B F D
左子树的后序序列:F D B
右子树的先序序列:G E H
右子树的中序序列:G E H
右子树的后序序列:H E G
最终得到的二叉树的后序序列为:F D B H E G C A