EC16-判断二叉树是否为完全二叉树¶

代码实现¶

C
// 函数 fun：判断二叉树是否为完全二叉树
// 参数：bt - 二叉树的根节点
bool fun(BiTree bt) {
    // 创建队列用于层次遍历
    BiTree que[maxsize];  // 队列数组
    int front = 0, rear = 0;  // 队列的头指针和尾指针

    // 如果根节点不为空，则将其入队
    if (bt != NULL) {
        que[++rear] = bt;  // 入队操作

        // 层次遍历循环
        while (front != rear) {
            bt = que[++front];  // 出队操作，获取队首元素

            // 如果当前节点不为空
            if (bt != NULL) {
                // 将左右子节点入队（即使子节点为空也要入队）
                que[++rear] = bt->lchild;
                que[++rear] = bt->rchild;
            } else {
                // 如果当前节点为空，检查队列中剩余元素
                // 在完全二叉树中，空节点后面不能有非空节点
                while (front != rear) {
                    // 检查队列中剩余的所有节点
                    if (que[++front] != NULL) {
                        // 如果发现非空节点，说明不是完全二叉树
                        return false;
                    }
                }
            }
        }
    }

    // 所有检查通过，是完全二叉树
    return true;
}

代码逻辑解析¶

1. 完全二叉树定义¶

完全二叉树的特点： - 除最后一层外，其它各层的节点数都达到最大值 - 最后一层的节点都集中在左侧 - 叶子节点只可能出现在最后两层

2. 算法核心思想¶

使用层次遍历（广度优先搜索）配合空节点检查： - 按层次顺序遍历所有节点（包括空节点） - 一旦遇到空节点，后续的所有节点都必须是空节点 - 如果在空节点后还发现非空节点，则不是完全二叉树

3. 关键步骤分析¶

步骤1：初始化队列

C
BiTree que[maxsize];  // 循环队列
int front = 0, rear = 0;  // 头尾指针

步骤2：层次遍历

C
while (front != rear) {
    bt = que[++front];  // 出队
    if (bt != NULL) {
        // 非空节点：将子节点入队
        que[++rear] = bt->lchild;
        que[++rear] = bt->rchild;
    } else {
        // 空节点：检查后续节点
        // ...
    }
}

步骤3：空节点后检查

C
while (front != rear) {
    if (que[++front] != NULL) {
        return false;  // 发现非空节点，不是完全二叉树
    }
}

时间复杂度分析¶

1. 遍历节点数¶

每个节点（包括空节点）最多入队和出队一次
设二叉树有 n 个节点，队列中最多有 O(n) 个元素

2. 操作复杂度¶

每次入队/出队操作：O(1)
每个节点的处理：O(1)

3. 总体时间复杂度¶

O(n) - 线性时间复杂度

空间复杂度分析¶

1. 队列空间¶

队列最多存储所有节点和空节点
在最坏情况下（完全二叉树的最后一层），队列大小约为 n

2. 其他空间¶

只使用了常量级别的额外变量

3. 总体空间复杂度¶

O(n) - 队列空间为主要开销

较难理解部分的说明¶

1. 为什么空节点后不能有非空节点？¶

完全二叉树的层次遍历特点：¶

Text Only

完全二叉树示例：
        1
       / \
      2   3
     / \ /
    4  5 6

层次遍历序列：1 2 3 4 5 6 NULL NULL NULL ...

非完全二叉树示例：
        1
       / \
      2   3
     /   / \
    4   5   6

层次遍历序列：1 2 3 4 NULL 5 6 ...
                    ↑     ↑
                 空节点后出现非空节点

2. 图解说明¶

假设二叉树结构：

Text Only
1 2 3 4 5	`1 / \ 2 3 / \ / 4 5 6`

层次遍历过程：

Text Only

队列状态变化：
初始：[1]
第1轮：出队1，入队2,3 → [2,3]
第2轮：出队2，入队4,5 → [3,4,5]  
第3轮：出队3，入队5,6 → [4,5,6]
第4轮：出队4，入队NULL,NULL → [5,6,NULL,NULL]
第5轮：出队5，入队NULL,NULL → [6,NULL,NULL,NULL,NULL]
第6轮：出队6，入队NULL,NULL → [NULL,NULL,NULL,NULL,NULL,NULL]

遇到第一个NULL后，检查剩余元素全是NULL → 是完全二叉树

延伸知识点¶

1. 改进版本 - 计数法¶

C
bool isCompleteBinaryTree_Count(BiTree root) {
    if (root == NULL) return true;

    Queue* queue = createQueue();
    enqueue(queue, root);
    bool foundNull = false;

    while (!isEmpty(queue)) {
        BiTree node = dequeue(queue);

        if (node == NULL) {
            foundNull = true;
        } else {
            if (foundNull) {
                // 在空节点后发现非空节点
                return false;
            }
            enqueue(queue, node->lchild);
            enqueue(queue, node->rchild);
        }
    }

    return true;
}

2. 基于节点编号的判断法¶

C
// 完全二叉树性质：如果按层次编号（从1开始）
// 对于任意节点i，其左子节点为2i，右子节点为2i+1
// 最大编号应该等于节点总数

int countNodes(BiTree root) {
    if (root == NULL) return 0;
    return 1 + countNodes(root->lchild) + countNodes(root->rchild);
}

bool isCompleteBinaryTree_Numbering(BiTree root) {
    if (root == NULL) return true;

    int totalNodes = countNodes(root);
    return isComplete(root, 1, totalNodes);
}

bool isComplete(BiTree node, int index, int totalNodes) {
    if (node == NULL) return true;

    if (index > totalNodes) return false;

    return isComplete(node->lchild, 2 * index, totalNodes) &&
           isComplete(node->rchild, 2 * index + 1, totalNodes);
}

3. 完全二叉树的其他性质¶

C
// 性质1：叶子节点只能出现在最后两层
bool checkLeafLevels(BiTree root) {
    if (root == NULL) return true;

    Queue* queue = createQueue();
    enqueue(queue, root);
    int maxLevel = 0;
    int leafLevel = -1;

    // 计算树的高度
    BiTree temp = root;
    while (temp) {
        maxLevel++;
        temp = temp->lchild;
    }

    // 检查叶子节点层次
    int currentLevel = 0;
    // ... 实现略
}

4. 完全二叉树的应用场景¶

堆数据结构：二叉堆通常用数组实现，基于完全二叉树性质
哈夫曼编码：构建最优前缀码的树结构
数据库索引：B+树的变种应用
并行计算：任务调度的树形结构

5. 性能对比分析¶

算法	时间复杂度	空间复杂度	优点	缺点
队列法	O(n)	O(n)	直观易懂	需要额外队列空间
编号法	O(n)	O(log n)	空间效率高	需要两次遍历
计数法	O(n)	O(n)	逻辑清晰	递归可能栈溢出

6. 边界情况处理¶

C
// 测试用例
void testCases() {
    // 空树
    assert(isComplete(NULL) == true);

    // 单节点树
    BiTree single = createNode(1);
    assert(isComplete(single) == true);

    // 满二叉树（也是完全二叉树）
    //       1
    //      / \
    //     2   3
    //    / \ / \
    //   4  5 6  7

    // 非完全二叉树
    //       1
    //      / \
    //     2   3
    //    /   / \
    //   4   5   6
}

这个算法体现了层次遍历和完全二叉树性质应用的经典思想，是树结构判断问题中的重要算法。