设一棵二叉树的先序序列: a b d f c e g h ,中序序列: b f d a g e h c
时间: 2023-04-26 18:00:20 浏览: 205
这棵二叉树的结构如下:
```
a
/ \
b c
/ \ / \
d f e g
\
h
```
其中,根节点为 a,左子树为 b d f,右子树为 c e g h。
相关问题
设一棵二叉树的先序序列: A B D F C E G H ,中序序列: B F D A G E H C 求它的后序序列
根据先序序列的第一个节点 A,可以确定该二叉树的根节点为 A。然后在中序序列中找到 A 的位置,将中序序列分成左右两个子序列:
左子序列:B F D
右子序列:G E H C
接下来对左右子序列分别递归进行同样的操作,直到序列中只剩下一个节点。具体过程如下:
左子树的先序序列:B D F
左子树的中序序列:B F D
左子树的后序序列:F D B
右子树的先序序列:G E H
右子树的中序序列:G E H
右子树的后序序列:H E G
最终得到的二叉树的后序序列为:F D B H E G C A
设一棵二叉树的先序序列: A B D F C E G H ,中序序列: B F D A G E H C,请画出这颗二叉树
根据二叉树的先序序列和中序序列可以唯一确定一棵二叉树,可以通过如下步骤构建:
1. 先序序列的第一个元素 A 是根节点,将其作为根节点;
2. 在中序序列中找到 A 的位置,A 左侧的序列 B F D 是左子树的中序序列,A 右侧的序列 G E H C 是右子树的中序序列;
3. 在先序序列中,根节点 A 后面的第一个元素 B 是左子树的根节点,将其作为 A 的左孩子;
4. 在左子树的先序序列 B F D 中,B 是根节点,B 后面的第一个元素 F 是 B 的左孩子,将其作为 B 的左孩子;
5. 在左子树的先序序列 B F D 中,F 之后没有其他元素,说明 F 没有左右孩子,返回上一层;
6. 在左子树的先序序列 B F D 中,B 的右侧元素 D 是 B 的右孩子,将其作为 B 的右孩子;
7. 在左子树的先序序列 B F D 中,D 的后面是元素 E,说明 D 没有左孩子,将 E 作为 D 的右孩子;
8. 在中序序列中,A 右侧的第一个元素 G 是右子树的根节点,将其作为 A 的右孩子;
9. 在右子树的先序序列 G H C 中,G 是根节点,G 后面没有其他元素,说明 G 没有左右孩子,返回上一层;
10. 在右子树的先序序列 G H C 中,H 是 G 的右孩子;
11. 在右子树的先序序列 G H C 中,C 是 H 的右孩子;
12. 在右子树的先序序列 G H C 中,C 之后没有其他元素,说明 C 没有左右孩子,返回上一层;
13. 最终得到如下的二叉树:
```
A
/ \
B G
/ \ \
F D H
/ \
E C
```