[简答题] (2)设一 棵二叉树的先序序列: ABDFC E GH ,中序序列:BF D AGE H C 1画出这棵二叉树。 2画出这棵二叉树的后序线索树。 3将这棵二叉树转换成对应的树(或森林)
时间: 2024-01-23 07:12:41 浏览: 28
1. 二叉树的结构如下图所示:
```
A
/ \
B C
/ \ \
D F H
/ \
E G
```
2. 后序线索树的结构如下图所示(其中粗实线表示线索):
```
H
/ \
B G C
/ \ /
D F E
\
A
```
3. 将二叉树转换成对应的森林,即将每个节点的左子树切断,形成多棵树。转换后的森林如下图所示:
```
A C
/ \
B H
/ \ /
D F E
/ \
E G
```
相关问题
设一棵二叉树的先序序列:ABDFCEGH,中序序列:BFDAGEHC。 画出这棵二叉树
根据先序序列和中序序列构造二叉树的步骤如下:
1. 先序序列的第一个元素为根节点,即A为根节点。
2. 在中序序列中找到根节点A,A左边的为左子树的中序序列,右边的为右子树的中序序列,即BFD为左子树的中序序列,GEHC为右子树的中序序列。
3. 根据左子树的中序序列BFD,可以得到左子树的先序序列为BFD,即B为左子树的根节点,F为B的左孩子,D为F的右孩子。
4. 根据右子树的中序序列GEHC,可以得到右子树的先序序列为GHEC,即G为右子树的根节点,H为G的左孩子,E为H的右孩子,C为E的右孩子。
5. 由此得到二叉树如下:
```
A
/ \
B G
/ / \
F H E
/ \
C H
```
设一棵二叉树的先序序列: A B D F C E G H ,中序序列: B F D A G E H C,请画出这颗二叉树
根据二叉树的先序序列和中序序列可以唯一确定一棵二叉树,可以通过如下步骤构建:
1. 先序序列的第一个元素 A 是根节点,将其作为根节点;
2. 在中序序列中找到 A 的位置,A 左侧的序列 B F D 是左子树的中序序列,A 右侧的序列 G E H C 是右子树的中序序列;
3. 在先序序列中,根节点 A 后面的第一个元素 B 是左子树的根节点,将其作为 A 的左孩子;
4. 在左子树的先序序列 B F D 中,B 是根节点,B 后面的第一个元素 F 是 B 的左孩子,将其作为 B 的左孩子;
5. 在左子树的先序序列 B F D 中,F 之后没有其他元素,说明 F 没有左右孩子,返回上一层;
6. 在左子树的先序序列 B F D 中,B 的右侧元素 D 是 B 的右孩子,将其作为 B 的右孩子;
7. 在左子树的先序序列 B F D 中,D 的后面是元素 E,说明 D 没有左孩子,将 E 作为 D 的右孩子;
8. 在中序序列中,A 右侧的第一个元素 G 是右子树的根节点,将其作为 A 的右孩子;
9. 在右子树的先序序列 G H C 中,G 是根节点,G 后面没有其他元素,说明 G 没有左右孩子,返回上一层;
10. 在右子树的先序序列 G H C 中,H 是 G 的右孩子;
11. 在右子树的先序序列 G H C 中,C 是 H 的右孩子;
12. 在右子树的先序序列 G H C 中,C 之后没有其他元素,说明 C 没有左右孩子,返回上一层;
13. 最终得到如下的二叉树:
```
A
/ \
B G
/ \ \
F D H
/ \
E C
```
相关推荐
![py](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)