简述什么是完全二叉树 ？
完全二叉树（Complete Binary Tree）是一种特殊的二叉树，它具有以下特性：
- 所有层都是完全填满的，除了可能的最后一层。 在最后一层，所有的节点都尽可能地集中在左边。
- 最后一层的节点如果不是全部填满，那么缺失的节点只能出现在层的右边，且最后一层的节点连续分布在最左边。
这意味着，如果你按层序（从上到下，从左到右）遍历完全二叉树的节点，就像在读一本书一样，你会发现没有跳过任何“页码”直到最后一“页”。如果最后一“页”不是满的，那么所有的“空位”都集中在右边。
特点
- 高效的利用空间：完全二叉树不像满二叉树那样要求每一层都完全填满，但它依然保持了较好的平衡性，因此在数组中表示时可以高效地利用空间。
- 数组表示简洁：完全二叉树可以非常容易地使用数组来表示，无需为节点间的链接使用额外的指针。对于数组中任意位置
i的元素，其左子节点位置为2*i+1，右子节点为2*i+2，父节点为(i-1)/2。
应用
完全二叉树在计算机科学中有许多重要应用，尤其是在数据结构和算法的设计中：
- 二叉堆：二叉堆是完全二叉树的一个典型应用，广泛用于实现优先队列。二叉堆通过维持完全二叉树的结构，使得插入和删除最大（或最小）元素的操作能够在O(log n)时间内完成。
- 树形数组和线段树：在处理某些特定的算法问题，如区间查询和更新操作时，完全二叉树的结构使得这些数据结构的实现更加高效。
与满二叉树和平衡二叉树的关系
- 满二叉树：是一种特殊的完全二叉树，其中每一层都完全填满，没有任何节点缺失。
- 平衡二叉树：如AVL树或红黑树，它们保持树的平衡以确保操作的效率，但不一定是完全二叉树。
总的来说，完全二叉树通过其结构特性在多种场景中提供了高效的操作性能，尤其是在通过数组实现时，由于其结构的规律性，使得相关操作更加简便和高效。