某二叉树的后序遍历为:DGEBHIFCA,中序遍历为:DBGEACHFI。画出这个树,并写出前序遍历。
时间: 2023-07-15 14:13:05 浏览: 49
首先,根据后序遍历的特点,该二叉树的根节点为最后一个节点 A。然后,我们可以在中序遍历中找到根节点 A,并根据它分出左右子树。
中序遍历:D B G E A C H F I
后序遍历:D G E B H I F C A
根据中序遍历可以得到左子树的节点为 D B G E 和右子树的节点为 C H F I。接下来,我们对左右子树进行同样的操作,重复上述步骤,直到构建出整个二叉树。
最终得到的二叉树如下图所示:
```
A
/ \
/ \
/ \
/ \
B C
/ \ / \
D E H F
\ /
G I
```
根据前序遍历的定义,根节点先遍历,然后是左子树的前序遍历,最后是右子树的前序遍历。因此,该二叉树的前序遍历为:A B D E G C H F I。
相关问题
已知二叉树的后序遍历序列:JGDHEBKLIFCA 中序遍历序列: DJGBEHACKILF 画出这棵二叉树的形态
根据已知的中序遍历序列和后序遍历序列,可以重构出这棵二叉树,具体过程如下:
1. 后序遍历序列的最后一个元素是根节点,即C是根节点。
2. 在中序遍历序列中找到根节点C的位置,C前面的是左子树节点,C后面的是右子树节点。
3. 在后序遍历序列中找到左子树的节点,即JGDHEBKLIF,这些节点是在C的左侧的。
4. 将JGDHEBKLIF拆分成两部分,前半部分JGDHEBK是左子树的后序遍历序列,后半部分LIF是右子树的后序遍历序列。
5. 对于左子树,其中序遍历序列为DJGBEHACK,再按照步骤1-4重构左子树;对于右子树,其中序遍历序列为ILF,重构右子树。
6. 将左右子树连到C上,得到完整的二叉树。
以下是重构后的二叉树形态:
```
C
/ \
/ \
/ \
/ \
J I
/ \ / \
G D L F
/ \ /
H E K
\
B
\
A
```
根据前序和中序遍历 构建二叉树,输出后序遍历 前序遍历:ABDECFG 中序遍历:DBEAFCG
根据前序和中序遍历构建二叉树的步骤如下:
1. 前序遍历的第一个元素是根节点,即A。
2. 在中序遍历中找到根节点A的位置,将中序遍历分为左子树和右子树两部分。
左子树的中序遍历为:DBE,右子树的中序遍历为:FCG。
3. 根据左子树的中序遍历长度,可以得知前序遍历中左子树的元素个数为3,即DBE。
前序遍历中,根节点后面的3个元素即为左子树的前序遍历,即BDE。
4. 根据左子树的前序遍历和中序遍历,可以递归构建左子树。
5. 同理,根据右子树的前序遍历和中序遍历,可以递归构建右子树。
6. 最后得到的二叉树的后序遍历即为左子树的后序遍历 + 右子树的后序遍历 + 根节点,即DBEGCF.
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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_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)