完全二叉树
一、课上练习
编程练习
- 完全二叉树的构建与遍历：L3251
二、知识总结
✨ 核心思想
在二叉树的分类中，完美二叉树（Perfect Binary Tree）、完整二叉树（Full Binary Tree）和完全二叉树（Complete Binary Tree）是常见的三种特定类型的二叉树，它们具有特定的结构特征。
完整二叉树（Full Binary Tree）
完整二叉树或称满二叉树，是指每个节点都没有子节点或恰有两个子节点的二叉树。换句话说，没有任何节点只有一个子节点的情况。
特点：
- 每个节点要么是叶子节点，要么具有两个子节点。
- 并不要求所有叶子节点处于同一层。
完美二叉树（Perfect Binary Tree）
完美二叉树是一种每个节点都有两个子节点，且所有叶节点都在同一层的二叉树。这意味着，除了叶子节点外，每个节点都必须有两个子节点。完美二叉树的每一层都是完全填满的，最底层的叶节点在视觉上形成一条直线。
特点：
- 在深度为 d 的完美二叉树中，共有 2^d - 1 个节点。
- 在深度为 d 的完美二叉树中，叶节点数量为 2^(d-1) 个。
完全二叉树（Complete Binary Tree）
完全二叉树是介于完美二叉树和满二叉树之间的结构，它可能与完美二叉树相似，但底部两层可以不完全填充，且所有叶子都尽可能地集中在左边。
特点：
- 除了最后一层外，每一层都被完全填充，并且所有叶子都集中在左侧。
- 最后一层的叶节点可能不完全填充，但填充从左到右进行。
✨ 应用场景
三种特殊二叉树各有不同的应用场景：
- 完美二叉树通常在需要均匀的二叉树结构时使用，如某些特定类型的树形网络。
- 完整二叉树有时用于特定的算法实现，其中节点的添加和删除操作相对少见，或者当树的平衡不是主要关注点时。
- 完全二叉树在实际应用中最为常见，特别是在实现二叉堆结构时，例如优先队列的实现。二叉堆经常用数组来表示完全二叉树，使得父节点和子节点之间的关系可以通过索引轻松计算。
✨ 完全二叉树的性质
完全二叉树是一种特殊的二叉树，它在多种数据结构和算法中有着广泛的应用，特别是在实现优先队列和二叉堆结构时。
结构性质
- 层级填充：在完全二叉树中，除了最后一层外，每一层都是完全填充的。这意味着，直到最后一层之前，每一层都有最大数量的节点（即第 i 层有 2^i 个节点，其中层级 i 从 0 开始计算）。
- 叶子节点集中：最后一层的叶子节点都靠左排列，这层可能没有完全填充。
- 高度：完全二叉树的高度为 log2(n) 向下取整，其中 n 是树中节点的数量。这表明完全二叉树是相对平衡的。
数学性质
- 节点总数：如果完全二叉树的高度为 h，则节点总数介于 2^h 到 2^(h+1) - 1 之间。
- 叶子节点数：如果最后一层填满，则叶子节点数为 2^h 个，否则少于 2^h 个，但多于 2^(h-1) 个。
- 非叶子节点数：非叶子节点总是等于 n/2 向下取整，其中 n 是树中节点的总数。
访问性质
在使用数组实现的完全二叉树中，给定一个位于索引 i 的节点（从 1 开始计数）：
- 父节点的索引为 i/2 向下取整。
- 左子节点的索引为 2i（如果存在）。
- 右子节点的索引为 2i + 1（如果存在）。
这些关系使得数组成为实现完全二叉树的一种高效方式，因为它们允许快速访问任何节点的父节点或子节点，无需额外的指针结构。
实现优势
- 内存高效：由于其层级结构和左填充性质，完全二叉树可以使用连续的内存块（如数组）进行有效表示，减少了内存开销。
- 性能优化：在堆结构中应用完全二叉树可以优化许多操作，如插入、删除和堆调整，这些操作的时间复杂度通常为 O(log n)，其中 n 是节点数量。
✨ 应用场景
完全二叉树的主要应用包括：
- 优先队列和堆：完全二叉树常用于实现二叉堆，进而用于构建优先队列，支持快速插入和删除最大或最小元素的操作。
- 堆排序算法：基于二叉堆的堆排序算法利用完全二叉树的性质进行高效的排序。
完全二叉树的这些性质使其在计算机科学的多个领域中都非常重要，尤其是在数据结构和算法设计中。理解这些性质有助于更好地掌握和应用相关的技术。
✨ 执行示例
下面展示如何将数据 [5, 3, 8, 1, 4, 7, 9, 2] 构建为一棵完全二叉树，并验证其性质。
使用数组存储（索引从 1 开始）：
数组：[_, 5, 3, 8, 1, 4, 7, 9, 2]
索引： 0 1 2 3 4 5 6 7 8对应的树结构：
15 (i=1)
2 / \
3 3 8 (i=2, 3)
4 / \ / \
5 1 4 7 9 (i=4, 5, 6, 7)
6 /
7 2 (i=8)验证完全二叉树性质：
- 节点总数 n = 8
- 树的高度 h = floor(log2(8)) = 3
- 非叶子节点数 = floor(8/2) = 4（节点 5, 3, 8, 1）
- 叶子节点数 = 8 - 4 = 4（节点 4, 7, 9, 2）
- 除最后一层外每层都满：第 0 层 1 个，第 1 层 2 个，第 2 层 4 个，第 3 层 1 个
- 最后一层的节点靠左排列：只有节点 2 在最左边
验证父子关系：
- 节点 2（索引 8）：父节点索引 = 8/2 = 4，即节点 1 -- 正确
- 节点 1（索引 4）：左子索引 = 4*2 = 8，即节点 2 -- 正确
- 节点 8（索引 3）：左子索引 = 6（节点 7），右子索引 = 7（节点 9）-- 正确
✨ 解题步骤详解
以"完全二叉树的构建与遍历"为例：
问题： 给定 n 个节点的值，按照完全二叉树的规则建树，输出遍历结果。
解题步骤：
- 存储方式选择：完全二叉树最适合用数组存储，因为节点编号和数组索引之间有明确的数学关系。
- 读入数据：将 n 个值依次存入数组 tree[1] 到 tree[n]。
- 遍历实现：
- 先序遍历：递归函数 preOrder(i)，先访问 tree[i]，再递归 preOrder(2i)，再递归 preOrder(2i+1)，当 i > n 时返回。
- 中序遍历：递归函数 inOrder(i)，先递归左子树，再访问当前节点，再递归右子树。
- 后序遍历：类似，改变访问顺序即可。
- 边界判断：递归时判断
if (i > n) return;即可，无需额外判断左右子节点是否存在。
关键优势： 完全二叉树用数组存储，不需要指针，节省内存且访问效率高。
✨ 常见错误
- 数组索引从 0 开始导致公式错误：如果索引从 0 开始，父子关系公式不同（左子 = 2i+1，右子 = 2i+2，父 = (i-1)/2）。建议统一从 1 开始，公式更简洁。
- 误认为完全二叉树就是满二叉树：完全二叉树的最后一层可以不满，但必须从左到右连续填充。满二叉树要求每个节点要么有 0 个子节点要么有 2 个。
- 数组开辟空间不够：n 个节点的完全二叉树，数组至少要开到 n+1 大小（索引 0 不用）。
- 遍历时递归终止条件写错：应该是
i > n而不是i >= n，因为第 n 个节点是有效节点。
三、课后练习
编程练习
- 对称二叉树：L3252