一个二叉树的先序序列是ABDGCEFH,中序序列是DGBAECHF,那么他的后序序列是什么(请给出图示证明)
时间: 2024-05-19 19:15:23 浏览: 13
该二叉树的后序序列为:DGEBHFCA。
证明如下图所示:
首先,从先序序列中得知根节点为A,然后在中序序列中找到根节点A的位置,将中序序列分为左子树和右子树,左子树的中序序列为DGB,右子树的中序序列为ECHF。
根据左右子树的大小,可以将先序序列分成两部分,分别为左子树的先序序列ABDGC和右子树的先序序列FEH。
对于左子树,根据同样的方法,可以得到左子树的根节点为B,左子树的中序序列为DG,左子树的先序序列为BDG,进而得到左子树的后序序列为DGB。
对于右子树,同样也可以得到右子树的根节点为F,右子树中序序列为EH,右子树的先序序列为FEH,进而得到右子树的后序序列为EHF。
综合左右子树的后序序列,可以得到整棵树的后序序列为DGEBHFCA。
相关问题
二叉树 先序遍历abdgcefh 中序遍历dbgaechf 后序遍历是什么
根据先序遍历和中序遍历构建二叉树,可以得到如下的二叉树结构:
```
a
/ \
b c
/ / \
d e f
\
g
/ \
h i
```
其中,根据先序遍历的顺序,a为根节点,b为左子树的根节点,d为左子树的左子树的根节点,g为左子树的右子树的根节点,c为右子树的根节点,e为右子树的左子树的根节点,f为右子树的右子树的根节点。根据中序遍历的顺序,d、b、g、a、e、c、h、g、i依次为二叉树各个子树的节点,因此可以确定二叉树的结构。根据后序遍历的顺序,可以得到二叉树的后序遍历结果为dgihfeca。
给定一个二叉树的先序序列ABDEGCHF,中序序列DBEGAHCF,要求输出二叉树的后序序列
根据二叉树的先序序列和中序序列可以构建出二叉树,具体步骤为:
1. 先序序列的第一个元素为根节点,即A。
2. 在中序序列中找到根节点A,根节点左侧为左子树的中序序列DBEG,右侧为右子树的中序序列HCF。
3. 统计左子树的节点个数,该个数即为左子树的先序序列ABDEG中除去根节点A后的节点个数。
4. 根据左子树的节点个数,在先序序列中找到左子树的先序序列ABDEG,右侧为右子树的先序序列CHF。
5. 递归处理左子树和右子树。
根据上述步骤,可以构建出如下二叉树:
```
A
/ \
/ \
B C
/ \ \
D E F
\
G
```
根据二叉树的后序遍历规则,后序序列应为:DGEBGHFCA。
因此,二叉树的后序序列为DGEBGHFCA。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](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)