Course playlist
线性数据结构 (4课)
队列
链表
向量
简单树 (3课)
树的定义和概念
树的表示和存储
二叉树的定义与性质
二叉树的表示与存储
二叉树的遍历
特殊树 (4课)
完全二叉树的定义与性质
完全二叉树的数组表示法
哈夫曼树,哈夫曼编码
二叉搜索树的定义和构造

利用完全二叉树 "节点编号连续" 的性质,将逻辑结构中的每个节点,按照 "层序遍历" 的顺序(从上到下,从左到右),依次存储到一个一维数组中。

考虑如下完全二叉树:
        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,则不存在。

1 完全二叉树的顺序存储方案,是指将完全二叉树的结点从上至下、从左至右依次存放到一个顺序结构的数组中。假定根结点存放在数组的 1 号位置,则第 k 号结点的父结点如果存在的话,应当存放在数组的( )号位置。
登录后查看选项
2 一个有 124 个叶子节点的完全二叉树,最多有( )个结点
登录后查看选项
3 在使用数组表示完全二叉树时,如果一个节点的索引为i (从0开始计数),那么其左子节点的索引通常是( )。
登录后查看选项
4 完全二叉树可以用数组连续高效存储。如果节点从 1 开始编号,则对有两个孩子节点的节点 i ,( )。
登录后查看选项
题目 对/错/率 难度 记录 通过
姓名 分数 提交时间 操作
158 50 2025-10-23 18:48 查看
158 25 2025-10-23 18:40 查看
158 25 2025-10-22 11:20 查看
158 0 2025-10-22 11:13 查看