EC13-使用层次遍历（广度优先搜索）计算二叉树的高度¶

代码实现¶

C
// 函数 level：使用层次遍历（广度优先搜索）计算二叉树的高度
// 参数：bt - 二叉树的根节点指针
// 返回值：二叉树的高度
int level(BiTree bt) {
    // 创建队列用于层次遍历
    BiTree que[maxsize];  // 队列数组
    int front = 0, rear = 0;  // 队列的头指针和尾指针
    int last = 1;         // 标记当前层的最后一个节点在队列中的位置
    int level = 0;        // 树的高度计数器

    que[++rear] = bt;  // 将根节点入队

    // 当队列不为空时继续遍历
    while (front != rear) {
        bt = que[++front];  // 出队一个节点

        // 将当前节点的左右子节点入队
        if (bt->lchild != NULL) {
            que[++rear] = bt->lchild;
        }
        if (bt->rchild != NULL) {
            que[++rear] = bt->rchild;
        }

        // 如果当前出队节点是当前层的最后一个节点
        if (front == last) {
            level++;           // 层数加1
            last = rear;       // 更新下一层的最后一个节点位置
        }
    }

    return level;  // 返回树的高度
}

代码逻辑解析¶

1. 层次遍历基本原理¶

使用队列实现广度优先搜索（BFS）
按照从上到下、从左到右的顺序访问节点
逐层处理每个节点

2. 关键变量说明¶

C
int front = 0, rear = 0;  // 队列的头尾指针（循环队列思想）
int last = 1;             // 标记当前层的最后一个节点位置
int level = 0;            // 当前层数（树的高度）

3. 层次控制机制¶

核心思想：按层处理节点 - last 变量标记当前层的最后一个节点在队列中的位置 - 当处理到该节点时，说明当前层已处理完毕 - 此时更新层数，并将 last 设置为下一层的最后一个节点位置

4. 算法执行流程¶

根节点入队
循环处理队列中的节点
每处理一个节点，将其子节点入队
当处理完当前层的最后一个节点时，层数加1
更新 last 为当前队列尾部位置（下一层的最后节点）

时间复杂度分析¶

1. 节点访问次数¶

每个节点恰好被访问一次
每个节点的左右子节点最多被检查一次
总的节点处理次数：n（节点数）

2. 队列操作复杂度¶

入队操作：O(1)
出队操作：O(1)
总操作次数：O(n)

3. 总体时间复杂度¶

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

空间复杂度分析¶

1. 队列空间使用¶

队列最大可能存储所有节点
在完全二叉树中，最后一层节点数约为 n/2
队列空间复杂度：O(n)

2. 额外变量空间¶

使用了常量级别的额外变量（front, rear, last, level）
空间复杂度：O(1)

3. 总体空间复杂度¶

O(n) - 队列可能存储最多 n 个节点

较难理解部分的说明¶

1. 层次控制机制详解¶

C
// 关键代码解释
if (front == last) {  // 处理到当前层的最后一个节点
    level++;          // 当前层处理完毕，层数加1
    last = rear;      // 下一层的最后一个节点位置
}

图解说明¶

假设二叉树结构如下：

Text Only
1 2 3 4 5	`A // 第1层 / \ B C // 第2层 / / \ D E F // 第3层`

执行过程：

Text Only

初始状态：
队列: [A]           front=0, rear=1, last=1

第1轮处理：
出队 A，入队 B,C
队列: [A, B, C]     front=1, rear=3, last=1
front(1) == last(1) → level=1, last=3

第2轮处理：
出队 B，入队 D
队列: [A, B, C, D]  front=2, rear=4, last=3
出队 C，入队 E,F
队列: [A, B, C, D, E, F] front=3, rear=6, last=3
front(3) == last(3) → level=2, last=6

第3轮处理：
出队 D, E, F（无子节点入队）
front=6 == last=6 → level=3, last=6

队列为空，结束
最终结果：level = 3

2. 队列边界处理¶

C
// 队列操作细节
que[++rear] = bt;        // 先增加 rear，再存储元素
bt = que[++front];       // 先增加 front，再取出元素

这是典型的队尾插入、队头删除的队列操作模式。

延伸知识点¶

1. 递归版本对比¶

C
// 递归计算树高度的经典方法
int getHeightRecursive(BiTree root) {
    if (root == NULL) return 0;

    int leftHeight = getHeightRecursive(root->lchild);
    int rightHeight = getHeightRecursive(root->rchild);

    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}
// 时间复杂度：O(n)
// 空间复杂度：O(h) - 递归栈深度

2. 改进的层次遍历版本¶

C
// 使用队列大小来判断层数
int levelImproved(BiTree bt) {
    if (bt == NULL) return 0;

    Queue* queue = createQueue();
    enqueue(queue, bt);
    int level = 0;

    while (!isEmpty(queue)) {
        int levelSize = getQueueSize(queue);  // 当前层的节点数
        level++;  // 层数加1

        // 处理当前层的所有节点
        for (int i = 0; i < levelSize; i++) {
            BiTree node = dequeue(queue);

            if (node->lchild) enqueue(queue, node->lchild);
            if (node->rchild) enqueue(queue, node->rchild);
        }
    }

    return level;
}

3. 层次遍历的其他应用¶

输出每层节点¶

C
void printLevelOrder(BiTree root) {
    if (root == NULL) return;

    BiTree queue[maxsize];
    int front = 0, rear = 0;
    queue[rear++] = root;

    while (front < rear) {
        int levelSize = rear - front;
        printf("Level: ");

        for (int i = 0; i < levelSize; i++) {
            BiTree node = queue[front++];
            printf("%c ", node->data);

            if (node->lchild) queue[rear++] = node->lchild;
            if (node->rchild) queue[rear++] = node->rchild;
        }
        printf("\n");
    }
}

计算每层节点数¶

C
int* countNodesPerLevel(BiTree root, int* maxLevel) {
    if (root == NULL) {
        *maxLevel = 0;
        return NULL;
    }

    int* levelCounts = (int*)calloc(1000, sizeof(int)); // 假设最大1000层
    BiTree queue[maxsize];
    int front = 0, rear = 0, level = 0;
    queue[rear++] = root;

    while (front < rear) {
        int levelSize = rear - front;
        levelCounts[level] = levelSize;
        level++;

        for (int i = 0; i < levelSize; i++) {
            BiTree node = queue[front++];
            if (node->lchild) queue[rear++] = node->lchild;
            if (node->rchild) queue[rear++] = node->rchild;
        }
    }

    *maxLevel = level;
    return levelCounts;
}

4. 循环队列优化¶

C
// 使用循环队列避免数组越界
#define MAXSIZE 1000
typedef struct {
    BiTree data[MAXSIZE];
    int front, rear;
} CircularQueue;

int levelCircularQueue(BiTree bt) {
    if (bt == NULL) return 0;

    CircularQueue q;
    q.front = q.rear = 0;
    int level = 0;
    int last = (q.rear + 1) % MAXSIZE;

    q.data[q.rear] = bt;
    q.rear = (q.rear + 1) % MAXSIZE;

    while (q.front != q.rear) {
        bt = q.data[q.front];
        q.front = (q.front + 1) % MAXSIZE;

        if (bt->lchild) {
            q.data[q.rear] = bt->lchild;
            q.rear = (q.rear + 1) % MAXSIZE;
        }
        if (bt->rchild) {
            q.data[q.rear] = bt->rchild;
            q.rear = (q.rear + 1) % MAXSIZE;
        }

        if (q.front == last) {
            level++;
            last = q.rear;
        }
    }

    return level;
}

5. 实际应用场景¶

文件系统：目录树的层级深度分析
组织架构：公司管理层级统计
游戏开发：技能树的深度计算
网络拓扑：路由跳数计算
编译器：语法树的嵌套层次分析

6. 性能对比总结¶

方法	时间复杂度	空间复杂度	优点	缺点
层次遍历	O(n)	O(n)	直观易懂，可扩展性强	空间消耗大
递归遍历	O(n)	O(h)	空间效率高	可能栈溢出

层次遍历求树高度的方法体现了广度优先搜索的核心思想，是树算法中的重要技术，特别适用于需要按层处理的场景。