Course playlist
利用完全二叉树 "节点编号连续" 的性质,将逻辑结构中的每个节点,按照 "层序遍历" 的顺序(从上到下,从左到右),依次存储到一个一维数组中。
考虑如下完全二叉树:
A
/ \
B C
/ \ /
D E F
数组表示(从 0 开始)
| 索引 i | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 值 | A | B | C | D | E | F |
验证(以 B 为例,i = 1):
- 父节点:
⌊(1−1)/2⌋ = 0→ A ✅ - 左孩子:
2×1+1 = 3→ D ✅ - 右孩子:
2×1+2 = 4→ E ✅
以 C 为例(i = 2):
- 父节点:
⌊(2−1)/2⌋ = ⌊0.5⌋ = 0→ A ✅ - 左孩子:
2×2+1 = 5→ F ✅ - 右孩子:
2×2+2 = 6 ≥ 6(总节点数 n=6)→ 不存在 ✅
情况 1:数组下标从 1 开始
设节点在数组中的下标为 i(1 ≤ i ≤ n):
- 父节点:
parent(i) = ⌊i / 2⌋ - 左孩子:
left(i) = 2i - 右孩子:
right(i) = 2i + 1
注意:若计算出的子节点下标 > n(总节点数),则该子节点不存在。
情况 2:数组下标从 0 开始(更常用在编程中)
设节点在数组中的下标为 i(0 ≤ i < n):
- 父节点:
parent(i) = ⌊(i - 1) / 2⌋ - 左孩子:
left(i) = 2i + 1 - 右孩子:
right(i) = 2i + 2
同样,若子节点下标 ≥ n,则不存在。
| 题目 | 对/错/率 | 难度 | 记录 | 通过 |
|---|