5. 某二叉树的中序遍历序列为DBKFIAHEJCG,后序遍历序为DKIFBHJEGCA。 (1)画出该二叉树; (2)写出该二叉树的前序遍历序列和层序遍历序列。
时间: 2023-07-24 16:17:26 浏览: 40
(1) 经过分析,该二叉树的根节点是最后一个后序遍历的节点,即A。由此可得到该二叉树的结构:
```
A
/ \
/ \
/ \
/ \
B C
\ / \
\ / \
D E F
/ \ \
G H I
\
J
```
(2) 该二叉树的前序遍历序列为ABDGEJCFIH,层序遍历序列为ABCDEFGHIJ。
相关问题
已知二叉树中序遍历序列为CBDFEGAMLNKJOPRQIHS, 后序遍历序列为CFGEDBMNLKRQPOJISHA,试画出此二叉树
根据二叉树遍历的特点,可以确定该二叉树的根节点为序列中的最后一个节点 "A"。然后在中序遍历中找到根节点的位置,根节点左边的序列为左子树的中序遍历序列,右边的序列为右子树的中序遍历序列。同样,在后序遍历中,根节点左边的序列为左子树的后序遍历序列,右边的序列为右子树的后序遍历序列。然后递归构造左右子树即可。
构造过程如下:
1. 根据中序遍历序列,确定根节点为 "A",并找到 "A" 在中序遍历序列中的位置。
2. 根据后序遍历序列,确定根节点为 "A",并找到 "A" 在后序遍历序列中的位置。
3. 根据中序遍历序列和后序遍历序列,确定左子树的中序遍历序列为 "CBDFEGM",左子树的后序遍历序列为 "CFGEDBM"。
4. 根据中序遍历序列和后序遍历序列,确定右子树的中序遍历序列为 "LNKJOPRQIHS",右子树的后序遍历序列为 "NLKRQPOJISH".
5. 递归构造左右子树,得到完整的二叉树。
最终的二叉树如下图所示:
```
A
/ \
/ \
/ \
/ \
C L
/ \ / \
/ \ / \
B D K N
/ \ / \
/ \ / \
F E J O
/ \ \
/ \ \
G M I
\
\
S
```
其中,节点的左子树在上方,右子树在下方。
已知二叉树的中序遍历序列为 GADCJEBIHF 后序遍历序列为 ADGEJIBFHC 则先序遍历序列为
根据中序遍历和后序遍历序列可以重构出原二叉树,进而得到先序遍历序列。具体过程如下:
1. 后序遍历序列的最后一个元素是根节点,即 H。
2. 在中序遍历序列中找到根节点 H 的位置,可以将中序遍历序列分成左子树和右子树两部分:
左子树:GADCJE
右子树:BI
3. 对于左子树,其后序遍历序列的最后一个元素是其根节点,即 E。同样地,在左子树的中序遍历序列中找到根节点 E 的位置,可以将左子树分成左子树和右子树两部分:
左子树:GADC
右子树:J
4. 对于右子树,其后序遍历序列的最后一个元素是其根节点,即 C。在右子树的中序遍历序列中找到根节点 C 的位置,可以将右子树分成左子树和右子树两部分:
左子树:BI
右子树:HF
5. 继续对左子树和右子树进行上述步骤,直到所有的节点都被处理完毕。
由此可得,重构出的二叉树如下所示:
```
H
/ \
/ \
E C
/ \ / \
G A B I
/ / \
D J F
```
最后,根据得到的二叉树,可以得到先序遍历序列为:
```
H E G A D C B I J F H
```