设一棵二叉树的先序序列: A B D F C E G H ,中序序列: B F D A G E H C,请画出这颗二叉树
时间: 2024-03-08 18:45:49 浏览: 108
二叉树的几种操作,包括递归先序建立二叉树、先序遍历、中序遍历、后序遍历、非递归的各种遍历
根据二叉树的先序序列和中序序列可以唯一确定一棵二叉树,可以通过如下步骤构建:
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
```
阅读全文