已知一棵二叉树的后序遍历序列为EICBGAHDF,中序遍历序列为CEIFGBADH,画出该二叉树
时间: 2023-06-23 16:46:17 浏览: 84
二叉树的示意图如下:
```
H
/ \
D F
/ \ \
I C G
/ \
E B
```
其中,根节点为`H`,左子树为`DIFCEB`,右子树为`FG`。
相关问题
一棵二叉树后序遍历序列为DABEC,中序遍历序列为DEBAC,则先序遍历序列为
根据二叉树遍历的性质,先序遍历序列的顺序是根节点、左子树、右子树。因此,我们可以通过已知的后序遍历序列和中序遍历序列来构建二叉树,并从中得到先序遍历序列。
根据中序遍历的性质,序列中根节点的位置左边为左子树的中序遍历序列,右边为右子树的中序遍历序列。在本例中,D是后序遍历序列的最后一个节点,因此D是根节点。在中序遍历序列中,D的位置为第4个,因此DEBA是左子树的中序遍历序列,C是右子树的根节点,因此AC是右子树的中序遍历序列。
接下来我们需要根据左子树和右子树的中序遍历序列及后序遍历序列来构建左右子树。对于左子树,后序遍历序列为ABED,中序遍历序列为DEBA。我们可以通过同样的方法来确定左子树的根节点为B,在中序遍历序列中B的位置为第2个,因此EDBA是左子树的后序遍历序列,EA是左子树的中序遍历序列。同理,对于右子树,后序遍历序列为C,中序遍历序列为AC。
现在我们已经得到了左右子树的先序遍历序列,可以递归地得到整个树的先序遍历序列为:D、B、E、A、C。
已知二叉树的后序遍历序列: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
```
阅读全文