用一个一维数组依次存放了一课完全二叉树的各结点:ABCDEFGHIJKL。请: (1)画出该二叉树。 (2)写出后序遍历该二叉树得到的序列。
时间: 2023-06-19 08:05:44 浏览: 44
根据完全二叉树的性质,可以将该二叉树表示为:
```
A
/ \
B C
/ \ / \
D E F G
/ \ / \ / \ /
H I J K L
```
该完全二叉树的后序遍历顺序为:H I J K D E B L F G C A
具体遍历过程如下:
1. 遍历左子树,得到序列:H I J K D E B
2. 遍历右子树,得到序列:L F G C
3. 将根节点 A 加入序列:H I J K D E B L F G C A
因此,该完全二叉树的后序遍历序列为 H I J K D E B L F G C A。
相关问题
用一维数组存放完全二叉树
一维数组可以用来存放完全二叉树。完全二叉树是一种特殊的二叉树,它的每个节点都按照从上到下、从左到右的顺序依次排列。我们可以使用数组来表示完全二叉树,其中数组的索引表示节点的位置,数组的值表示节点的值。
具体的存储方式如下:
1. 对于完全二叉树中的第i个节点,它的左子节点的索引为2i,右子节点的索引为2i+1。
2. 对于完全二叉树中的第i个节点,它的父节点的索引为i/2(向下取整)。
下面是一个示例,演示如何使用一维数组存放完全二叉树,并实现先序、中序和后序遍历:
```python
# 定义完全二叉树的一维数组表示
tree = [None, 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J']
# 先序遍历
def preorder(root):
if root <= len(tree) - 1:
if tree[root] is not None:
print(tree[root], end=' ')
preorder(root * 2) # 遍历左子树
preorder(root * 2 + 1) # 遍历右子树
# 中序遍历
def inorder(root):
if root <= len(tree) - 1:
if tree[root] is not None:
inorder(root * 2) # 遍历左子树
print(tree[root], end=' ')
inorder(root * 2 + 1) # 遍历右子树
# 后序遍历
def postorder(root):
if root <= len(tree) - 1:
if tree[root] is not None:
postorder(root * 2) # 遍历左子树
postorder(root * 2 + 1) # 遍历右子树
print(tree[root], end=' ')
# 演示先序、中序和后序遍历
print("先序遍历结果:")
preorder(1)
print("\n中序遍历结果:")
inorder(1)
print("\n后序遍历结果:")
postorder(1)
```
输出结果:
```
先序遍历结果:
A B D H I E J C F G
中序遍历结果:
H D I B J E A F C G
后序遍历结果:
H I D J E B F G C A
```
画完全二叉树:有7个叶结点,没有度为1结点的完全二叉树完全二叉树:
画完全二叉树时,我们需要先确定二叉树的深度和节点数目。对于没有度为1结点的完全二叉树,其叶子节点数目为7,则总节点数目为 $2*7-1=13$。因此,该完全二叉树深度为 $\lceil log_2 13 \rceil = 4$。
接下来,我们可以按照以下步骤画出这棵完全二叉树:
1. 先画出第一层,只有一个根节点。
2. 接着画出第二层,有两个节点。
3. 继续画出第三层,有四个节点。
4. 最后画出第四层,有一个节点。
画出完全二叉树如下:
```
o
/ \
o o
/ \
o o
/ \
o o
```