我们知道如何按照三种深度优先次序来周游一棵二叉树,来得到中根序列、前根序列和后根序列。反过来,如果给定二叉树的中根序列和后根序列,或者给定中根序列和前根序列,可以重建一二叉树。本题输入一棵二叉树的中根序列和后根序列,要求在内存中重建二叉树,最后输出这棵二叉树的前根序列。 用不同的整数来唯一标识二叉树的每一个结点,下面的二叉树 中根序列是9 5 32 67 后根序列9 32 67 5 前根序列5 9 67 32 输入 两行。第一行是二叉树的中根序列,第二行是后根序列。每个数字表示的结点之间用空格隔开。结点数字范围0~65535。暂不必考虑不合理的输入数据。 输出 一行。由输入中的中根序列和后根序列重建的二叉树的前根序列。每个数字表示的结点之间用空格隔开。 样例输入 9 5 32 67 9 32 67 5 样例输出 5 9 67 32
时间: 2024-04-29 09:19:23 浏览: 9
根据中序序列和后序序列重建二叉树的过程如下:
1. 后序序列的最后一个元素一定是二叉树的根节点。
2. 在中序序列中找到根节点的位置,该位置左侧的元素都是根节点的左子树,右侧的元素都是根节点的右子树。
3. 根据左子树的元素个数,可以在后序序列中确定左子树和右子树的边界。
4. 递归构建左子树和右子树。
重建二叉树的代码实现如下:
相关问题
已知一棵二叉树的便利序列如下画出据此构造的二叉树 中根次序便利序列CDBEGFHANMOLKPQSRJIT 后根次序便利序列 DCGHFEBNOMLSRQPKJTIA
根据中根次序便利序列,我们可以确定二叉树的结构,再根据后根次序便利序列,我们可以确定每个节点的位置。具体步骤如下:
1. 中根次序便利序列为 CDBEGFHANMOLKPQSRJIT。根据中根次序便利序列,我们可以确定根节点为I。将中根次序便利序列分为左子树和右子树两部分:
左子树:CDBEGFHANMOLKPQSR
右子树:JT
2. 后根次序便利序列为DCGHFEBNOMLSRQPKJTIA。根据后根次序便利序列,最后一个节点为根节点I,倒数第二个节点为右子树的节点T。将后根次序便利序列分为左子树和右子树两部分:
左子树:DCGHFEBNOMLSRQPK
右子树:TIA
3. 对于左子树,它的后根次序便利序列为DCGHFEBNOMLSRQPK,最后一个节点为K,倒数第二个节点为Q,因此K为左子树的根节点。将左子树的中根次序便利序列和后根次序便利序列分为左子树和右子树两部分:
左子树:DCGHFEBNOMLSR
右子树:QPK
4. 对于左子树的左子树,它的后根次序便利序列为DCGHFEBNOMLSR,最后一个节点为R,倒数第二个节点为S,因此R为左子树的左子树的根节点。将左子树的左子树的中根次序便利序列和后根次序便利序列分为左子树和右子树两部分:
左子树:DCGHFEBNO
右子树:LSR
5. 对于左子树的左子树的右子树,它的后根次序便利序列为LSR,最后一个节点为R,倒数第二个节点为S,因此R为左子树的左子树的右子树的根节点。将左子树的左子树的右子树的中根次序便利序列和后根次序便利序列分为左子树和右子树两部分:
左子树:L
右子树:SR
6. 对于左子树的左子树的右子树的右子树,它的后根次序便利序列为SR,最后一个节点为R,倒数第二个节点为S,因此R为左子树的左子树的右子树的右子树的根节点。
7. 对于左子树的右子树,它的后根次序便利序列为QPK,最后一个节点为K,倒数第二个节点为P,因此K为左子树的右子树的根节点。将左子树的右子树的中根次序便利序列和后根次序便利序列分为左子树和右子树两部分:
左子树:Q
右子树:PK
8. 对于左子树的右子树的右子树,它的后根次序便利序列为PK,最后一个节点为K,倒数第二个节点为P,因此K为左子树的右子树的右子树的根节点。
9. 对于右子树,它的后根次序便利序列为TIA,最后一个节点为A,倒数第二个节点为I,因此A为右子树的根节点。将右子树的中根次序便利序列和后根次序便利序列分为左子树和右子树两部分:
左子树:T
右子树:I
因此,据此构造的二叉树如下图所示:
```
I
/ \
/ \
K A
/ \ \
C Q T
\ /
E J
/ \ / \
D G M S
/ \
B R
\
P
```
请你帮我根据二叉树的中根次序遍历序列和后根的次序遍历序列画出二叉树图
好的,让我们来画一下吧。
假设中根次序遍历序列为:[D, B, E, A, F, C],后根次序遍历序列为:[D, E, B, F, C, A]。
首先,我们可以根据后根次序遍历序列的最后一个节点 A,确定它为根节点。然后,我们在中根次序遍历序列中找到 A,将序列分为左子树和右子树两部分:
左子树的中根次序遍历序列为:[D, B, E],右子树的中根次序遍历序列为:[F, C]。
接下来,我们需要确定左子树和右子树的根节点。根据后根次序遍历序列,我们可以找到左子树的根节点为 E,右子树的根节点为 C。
最后,我们再依次确定左子树和右子树的结构,即可画出完整的二叉树图。最终的结果如下图所示:
```
A
/ \
B C
/ \
D E
\
F
```