设一棵二叉树的先序序列:ABDFCEGH,中序序列:BFDAGEHC。 画出这棵二叉树
时间: 2023-12-05 18:39:01 浏览: 1051
根据先序序列和中序序列构造二叉树的步骤如下:
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
```
相关问题
一棵二叉树的先序序列:abdfcegh,中序序列:bfdagehc。该二叉树中右子树的根结点是()。
根据二叉树遍历的性质,先序序列的第一个元素是根节点,即a是该二叉树的根节点。在中序序列中找到a,可以将中序序列分成左右两部分:左边是该二叉树的左子树的中序遍历序列,右边是该二叉树的右子树的中序遍历序列。
中序序列:bfdagehc
先序序列:abdfcegh
根据中序序列的划分,可以将先序序列也分成两部分:左边是该二叉树的左子树的先序遍历序列,右边是该二叉树的右子树的先序遍历序列。
左子树的先序序列:bdf
左子树的中序序列:bfda
右子树的先序序列:cegh
右子树的中序序列:gehc
由此可以得到该二叉树的结构,如下所示:
```
a
/ \
b c
/ \ \
d f e
\
g
/ \
h c
```
因此,该二叉树右子树的根节点是e。
一棵二叉树的先序序列: abdfcegh,中序序列:bfdagehc。后序遍历序列为( )。 A. abcdefg B. ghecfdba C. fdbgheca D. fdbaghec
### 回答1:
根据先序序列的第一个节点确定根节点,即a为根节点。根据中序序列,找到根节点所在位置,即b在左子树,f在右子树。然后继续在左右子树中递归查找。
左子树的先序序列为:bdf,中序序列为:bfdgah,右子树的先序序列为:cegh,中序序列为:cefdhb。
左子树的后序遍历为:dfbgah,右子树的后序遍历为:cehg,因此整个二叉树的后序遍历序列为:dfbgahcehg。
因此答案为B选项:ghecfdba。
### 回答2:
根据二叉树的遍历顺序特点,可以得出以下规律:
1. 先序遍历的第一个元素为根节点。
2. 中序遍历的根节点的左边为左子树的中序遍历序列,右边为右子树的中序遍历序列。
3. 后序遍历的根节点的左边为左子树的后序遍历序列,右边为右子树的后序遍历序列。
根据给定的先序序列 "abdfcegh" 和中序序列 "bfdagehc",我们可以分析得出以下结论:
1. 先序序列 "abdfcegh" 的第一个元素为根节点,即为 "a"。
2. 在中序序列 "bfdagehc" 中找到根节点元素 "a",可以将中序序列分为左子树和右子树的序列。
左子树的中序序列为 "bfd",右子树的中序序列为 "gehc"。
同时,根据左子树和右子树的节点数量,我们可以得知左子树的先序序列为 "bdf",右子树的先序序列为 "cegh"。
3. 对于左子树的遍历,根据先序序列 "bdf" 和中序序列 "bfd",可以得出左子树的后序遍历序列为 "bfd"。
对于右子树的遍历,根据先序序列 "cegh" 和中序序列 "gehc",可以得出右子树的后序遍历序列为 "gehc"。
4. 综上所述,整棵树的后序遍历序列为 "bfdgehc"。
因此,答案为 D. fdbaghec。
### 回答3:
根据二叉树的先序序列为abdfcegh和中序序列为bfdagehc,我们可以确定根节点是a。根据中序序列的划分,我们可以将二叉树分为左子树和右子树。左子树的先序序列为bdf,中序序列为bfd,右子树的先序序列为cegh,中序序列为agehc。再根据左子树的先序序列为bdf和中序序列为bfd,可以确定左子树的根节点为b。根据右子树的先序序列为cegh和中序序列为agehc,可以确定右子树的根节点为c。
接下来,我们需要确定左子树和右子树的后序遍历序列。根据先序遍历序列和中序遍历序列的关系,我们可以确定左子树的后序遍历序列为fdb,右子树的后序遍历序列为gheca。
综上所述,该二叉树的后序遍历序列为fdbgheca,所以答案选项为D. fdbaghec。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)