数据结构

完全二叉树（Complete Binary Tree）是一种特殊的二叉树，具有以下主要特点：

  1. 定义：

    • 在一颗完全二叉树中，除了最后一层之外的所有层都被完全填满，并且最后一层的节点都尽可能地靠左。

  2. 结构特点：

    • 对于一个高度为 h 的完全二叉树：

      • 最多有 2^h -1 个节点。

      • 叶子节点集中在最底层，最后一层的所有节点都在最左边的位置。

      • 所有的叶子节点都在同一层或仅相差一层。

  3. 完美二叉树（Perfect Binary Tree） ：

    • 如果完全二叉树的最后一层也全部填满，则称为完美二叉树。完美二叉树的特点是每个非叶节点都有两个子节点，且所有叶节点在同一层。

  4. 数组表示：

    • 完全二叉树非常适合用数组来表示。给定一个根节点为 index 0 的完全二叉树，其子节点的索引可以通过以下公式计算：

      • 左子节点的索引: 2×index+1

      • 右子节点的索引: 2×index+2

  5. 高度和层数：

    • 在完全二叉树中，高度h和节点数n的关系为：

      • 2^{h−1}≤n<2^h

      • h = \lfloor \log_2n \rfloor + 1 或 h = \lceil \log_2(n+1) \rceil

  6. 应用

    • 完全二叉树在计算机科学中有许多重要的应用，包括堆（Heap）数据结构、优先队列等。
    • 二叉堆是一种特殊的完全二叉树，其中每个节点的值都大于或等于其子节点的值（最大堆），或者小于或等于其子节点的值（最小堆）。

示例

以下是一个高度为3的完全二叉树示例：

        1
      /   \
     2     3
    / \   /
   4   5 6

在这个例子中：

  • 第一层有1个节点。
  • 第二层有2个节点。
  • 第三层有3个节点，且所有节点都尽可能地靠左。

发表评论