先序遍历。ABDFCEGH,中序遍历:BFDAGEHC,画出二叉树
时间: 2023-07-21 15:43:48 浏览: 81
我们可以通过已知的先序遍历和中序遍历来构造二叉树。具体步骤如下:
1. 先序遍历的第一个节点是根节点,即 A。
2. 在中序遍历中找到根节点 A,它将中序遍历分为两部分:BFD 和 GEHC。
3. 根据步骤 2 中的结果,我们可以分别得到左子树和右子树的先序遍历和中序遍历:
- 左子树的先序遍历为 BDF,中序遍历为 BFD。
- 右子树的先序遍历为 CEGH,中序遍历为 GEHC。
4. 重复步骤 1~3,递归构造左右子树。
最终得到的二叉树如下:
```
A
/ \
B C
/ \ \
D F E
/ /
G H
```
相关问题
一颗二叉树的先序遍历为abdfcegh,中序序列为bfdagehc 转换成森林
根据先序遍历和中序遍历构造出该二叉树,然后将该二叉树转换成森林。具体步骤如下:
1. 根据先序遍历确定该二叉树的根节点为a。
2. 在中序遍历中找到根节点a,将中序遍历分为两个部分,左子树的中序遍历为bfd,右子树的中序遍历为gehc。
3. 根据左子树的中序遍历bfd和左子树的先序遍历bdfe构造左子树,右子树的中序遍历gehc和右子树的先序遍历cegh构造右子树。
4. 将左右子树分别转换成森林,得到两棵树,将它们作为根节点a的左右子树。
最终得到的森林如下图所示:
```
a c
/ \ \
b d e
/ \ \
f e g
/ \ \
c g h
/ \
h d
```
一棵二叉树的先序序列:abdfcegh,中序序列:bfdagehc。该二叉树中右子树的根结点是()。
根据二叉树遍历的性质,先序序列的第一个元素是根节点,即a是该二叉树的根节点。在中序序列中找到a,可以将中序序列分成左右两部分:左边是该二叉树的左子树的中序遍历序列,右边是该二叉树的右子树的中序遍历序列。
中序序列:bfdagehc
先序序列:abdfcegh
根据中序序列的划分,可以将先序序列也分成两部分:左边是该二叉树的左子树的先序遍历序列,右边是该二叉树的右子树的先序遍历序列。
左子树的先序序列:bdf
左子树的中序序列:bfda
右子树的先序序列:cegh
右子树的中序序列:gehc
由此可以得到该二叉树的结构,如下所示:
```
a
/ \
b c
/ \ \
d f e
\
g
/ \
h c
```
因此,该二叉树右子树的根节点是e。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)