【入门级-数据结构-3、特殊树：完全二叉树的定义与基本性质】

一、完全二叉树的严格定义
完全二叉树（Complete Binary Tree）是二叉树中极具规律性的特殊结构。
完全二叉树需满足两个核心条件：
除最后一层外，每一层的节点数都达到最大值（即第k层有2^(k-1)个节点，k≥1）；
最后一层的节点从左到右连续填充，且仅缺少右侧的若干节点（最后一层的节点都靠左排列，无空缺）。

二、完全二叉树的核心性质
以下性质均基于 “节点编号规则”：对完全二叉树的节点按层序遍历（从上到下、从左到右） 从1开始编号（也可从 0 开始，需注意公式调整）。
性质 1：节点总数与高度的关系
设完全二叉树的高度为h（根节点为第 1 层，高度≥1），节点总数为n：
高度的下界：h = ⌊log₂n⌋ + 1（⌊x⌋表示向下取整）；
例：n=6时，log₂6≈2.58，h=2+1=3；
节点数的范围：2^(h-1) ≤ n ≤ 2^h - 1；
下界：最后一层只有 1 个节点（如h=3时，n≥4）；
上界：满二叉树（如h=3时，n≤7）。

性质 2：父节点与子节点的编号关系（核心！）
若节点编号为i（i≥1），则：
左子节点编号：2i（若2i ≤ n，否则无左子节点）；
右子节点编号：2i + 1（若2i + 1 ≤ n，否则无右子节点）；
父节点编号：⌊i/2⌋（i>1；若i=1，为根节点，无父节点）。

性质 3：叶子节点的判定与数量
（1）叶子节点的快速判定
编号为i的节点是叶子节点，当且仅当：i > ⌊n/2⌋（n为总节点数）。例：n=6时，⌊6/2⌋=3，编号4、5、6均为叶子节点（与示例一致）。
（2）叶子节点的数量
设完全二叉树节点总数为n：
若n为偶数：叶子节点数 = n/2；
若n为奇数：叶子节点数 = (n+1)/2；
统一公式：叶子节点数 = ⌈n/2⌉（⌈x⌉表示向上取整）。
例：n=6（偶）→ 3 个叶子；n=7（奇）→ 4 个叶子。

性质 4：度为 1 的节点数量
完全二叉树中，度为 1 的节点（只有一个子节点）数量只能是 0 或 1：
若n为偶数：度为 1 的节点数 = 1（最后一个非叶子节点只有左子节点）；
若n为奇数：度为 1 的节点数 = 0（所有非叶子节点都有左右子节点）。
例：n=6（偶）→ 度为 1 的节点是 3（只有左子节点 6）；n=7（奇）→ 无度为 1 的节点。

性质 5：节点的深度与高度
深度：根节点深度为 1，节点i的深度 = ⌊log₂i⌋ + 1；
高度：叶子节点高度为 1，完全二叉树的高度 = 根节点的高度 = ⌊log₂n⌋ + 1；
推论：完全二叉树中，深度为k的节点编号范围是2^(k-1) ~ 2^k - 1。