二叉树的数组表示

以下是二叉树的结构：

1
2
3
4
5
6
7
         A
      /     \
    B         C
   / \       / \
  D   E     F   G
 / \     \
H   I     J

数组表示

数组构造规则：

  1. 层次遍历（从上到下，从左到右），每个节点都按照对应位置存入数组。
  2. 如果某个位置的子节点缺失，用 None 占位。

用数组表示上述二叉树：

1
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', None, 'J', None, None, None, None]

如何理解：

  • 索引 0 存储根节点 A。
  • 索引 1 存储 A 的左子节点 B；索引 2 存储 A 的右子节点 C。
  • 索引 3 和 4 分别存储 B 的左子节点 D 和右子节点 E。
  • 索引 5 和 6 分别存储 C 的左子节点 F 和右子节点 G。
  • 索引 7 和 8 分别存储 D 的左子节点 H 和右子节点 I。
  • 索引 9 是 E 的左子节点（缺失，用 None 占位）。
  • 索引 10 存储 E 的右子节点 J。
  • 后面索引 11 到 14 是 F 和 G 的子节点（均为空，用 None 占位）。

数组中索引的关系

给定节点索引 i：

  1. 左子节点：索引为 2 * i + 1。
  2. 右子节点：索引为 2 * i + 2。
  3. 父节点：索引为 (i - 1) // 2。

例如：

  • 节点 B 在索引 1：
    • 左子节点是 D，索引为 2 * 1 + 1 = 3。
    • 右子节点是 E，索引为 2 * 1 + 2 = 4。
  • 节点 E 在索引 4：
    • 左子节点为 None，索引为 9。
    • 右子节点是 J，索引为 10。

二叉树的遍历实现

我们接下来实现 前序遍历、中序遍历、后序遍历 和 层次遍历，并直接从数组中解析出结果。

遍历代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# 二叉树的数组表示
tree = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', None, 'J', None, None, None, None]

# 前序遍历（递归）
def preorder_traversal_array(tree, index):
    if index >= len(tree) or tree[index] is None:
        return []
    return [tree[index]] + preorder_traversal_array(tree, 2 * index + 1) + preorder_traversal_array(tree, 2 * index + 2)

# 中序遍历（递归）
def inorder_traversal_array(tree, index):
    if index >= len(tree) or tree[index] is None:
        return []
    return inorder_traversal_array(tree, 2 * index + 1) + [tree[index]] + inorder_traversal_array(tree, 2 * index + 2)

# 后序遍历（递归）
def postorder_traversal_array(tree, index):
    if index >= len(tree) or tree[index] is None:
        return []
    return postorder_traversal_array(tree, 2 * index + 1) + postorder_traversal_array(tree, 2 * index + 2) + [tree[index]]

# 层次遍历（广度优先）
def level_order_traversal_array(tree):
    return [node for node in tree if node is not None]

# 打印遍历结果
print("前序遍历:", preorder_traversal_array(tree, 0))
print("中序遍历:", inorder_traversal_array(tree, 0))
print("后序遍历:", postorder_traversal_array(tree, 0))
print("层次遍历:", level_order_traversal_array(tree))

输出结果

1
2
3
4
前序遍历: ['A', 'B', 'D', 'H', 'I', 'E', 'J', 'C', 'F', 'G']
中序遍历: ['H', 'D', 'I', 'B', 'E', 'J', 'A', 'F', 'C', 'G']
后序遍历: ['H', 'I', 'D', 'J', 'E', 'B', 'F', 'G', 'C', 'A']
层次遍历: ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J']

数组表示的优缺点

优点

  1. 索引访问快速：通过索引关系，能快速找到父节点或子节点，特别适合需要频繁查找关系的操作。
  2. 简洁表示：数组在表示 完全二叉树 时无需额外空间，所有节点按顺序排列，无需指针。
  3. 易于序列化和存储：二叉树可以直接转换为一个数组存储或传递，尤其是在网络传输或持久化时非常方便。

缺点

  1. 浪费空间：对于不完全或不平衡的二叉树，需要大量的 None 占位，浪费空间。例如，G 的子节点全为空，数组中填充了许多 None。
  2. 不灵活：数组的大小在初始化时需要规划好，插入或删除节点时需要重新调整数组，效率较低。
  3. 不适合深度不平衡的树：对于深度较大的不平衡树（例如左斜树或右斜树），数组会极其稀疏，浪费大量存储空间。

总结

数组表示二叉树适用于 完全二叉树 或 接近完全二叉树，对于深度大且不平衡的二叉树不太合适。None 在数组中用于占位以保证层次关系，这种方式虽然浪费了一些空间，但换取了简化的父子关系操作。