EC12-使用层次遍历计算二叉树中叶子节点的个数¶

代码实现¶

C
// 函数 level：使用层次遍历计算二叉树中叶子节点的个数
// 参数：bt - 二叉树根节点指针，n - 指向叶子节点计数器的指针
void level(BiTree bt, int *n) {
    BiTree que[maxsize];  // 创建队列数组，用于层次遍历
    int front = 0, rear = 0;  // 初始化队列的头指针和尾指针

    // 检查根节点是否为空
    if (bt != NULL) {
        que[++rear] = bt;  // 将根节点入队（rear 先自增再赋值）

        // 层次遍历循环：当队列不为空时继续
        while (front != rear) {
            bt = que[++front];  // 出队一个节点（front 先自增再取值）

            // 判断是否为叶子节点：左右子树都为空
            if (!bt->lchild && !bt->rchild) {
                ++(*n);  // 如果是叶子节点，计数器加1
            }

            // 将左子节点入队（如果存在）
            if (bt->lchild != NULL) {
                que[++rear] = bt->lchild;
            }

            // 将右子节点入队（如果存在）
            if (bt->rchild != NULL) {
                que[++rear] = bt->rchild;
            }
        }
    }
}

代码逻辑解析¶

1. 层次遍历基本原理¶

使用队列作为辅助数据结构
按照从上到下、从左到右的顺序访问节点
保证同一层的节点在相邻层节点之前被访问

2. 队列操作机制¶

C
// 入队操作
que[++rear] = node;  // rear 先自增，然后将节点放入队列

// 出队操作  
bt = que[++front];   // front 先自增，然后取出队列中的节点

队列状态示例：

Text Only
1 2 3	`初始状态：front=0, rear=0 (空队列) 入队A后：front=0, rear=1, que[1]=A 出队A后：front=1, rear=1 (空队列)`

3. 叶子节点判断¶

C
// 叶子节点定义：没有左右子树的节点
if (!bt->lchild && !bt->rchild) {
    ++(*n);  // 计数器加1
}

4. 遍历流程¶

根节点入队
循环出队节点
判断是否为叶子节点
将子节点入队
直到队列为空

时间复杂度分析¶

1. 节点访问次数¶

每个节点恰好被访问一次（入队和出队各一次）
设二叉树有 n 个节点，则总访问次数为 n

2. 每次操作复杂度¶

出队操作：O(1)
叶子节点判断：O(1)
入队操作：O(1)

3. 总体时间复杂度¶

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

空间复杂度分析¶

1. 队列空间使用¶

队列最大可能存储的节点数取决于树的宽度
最坏情况：完全二叉树的最后一层，节点数约为 n/2
队列空间复杂度：O(w)，其中 w 是树的最大宽度

2. 其他空间使用¶

只使用了常量级别的额外变量（front, rear）

3. 总体空间复杂度¶

O(w)，其中 w 是树的最大宽度在最坏情况下为 O(n)

较难理解部分的说明¶

1. 队列指针操作细节¶

C
// 队列操作示例
初始：front=0, rear=0

入队A：rear=1, que[1]=A
入队B：rear=2, que[2]=B  
入队C：rear=3, que[3]=C

出队A：front=1, bt=que[1]=A
出队B：front=2, bt=que[2]=B

2. 图解说明¶

假设二叉树结构如下：

Text Only
1 2 3 4 5	`A // 非叶子节点 / \ B C // B:叶子节点, C:非叶子节点 / \ D E // D,E:叶子节点`

层次遍历过程：

Text Only

步骤1: 队列=[A], front=0, rear=1
       出队A, A不是叶子, 入队B,C

步骤2: 队列=[B,C], front=1, rear=3
       出队B, B是叶子, n=1

步骤3: 队列=[C], front=2, rear=3  
       出队C, C不是叶子, 入队D,E

步骤4: 队列=[D,E], front=3, rear=5
       出队D, D是叶子, n=2

步骤5: 队列=[E], front=4, rear=5
       出队E, E是叶子, n=3

结束: 队列为空, 叶子节点总数=3

延伸知识点¶

1. 改进版本 - 使用动态队列¶

C
// 使用循环队列避免空间浪费
typedef struct {
    BiTree* data;
    int front, rear;
    int capacity;
} CircularQueue;

void levelImproved(BiTree bt, int *n) {
    if (bt == NULL) return;

    CircularQueue* queue = createCircularQueue(maxsize);
    enqueue(queue, bt);

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

        // 判断叶子节点
        if (!node->lchild && !node->rchild) {
            ++(*n);
        }

        // 子节点入队
        if (node->lchild) enqueue(queue, node->lchild);
        if (node->rchild) enqueue(queue, node->rchild);
    }

    destroyQueue(queue);
}

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

C
// 计算树的高度
int getHeight(BiTree bt) {
    if (bt == NULL) return 0;

    BiTree que[maxsize];
    int front = 0, rear = 0;
    int height = 0;
    int levelCount = 1; // 当前层节点数

    que[++rear] = bt;

    while (front != rear) {
        while (levelCount > 0) {
            bt = que[++front];
            levelCount--;

            if (bt->lchild) que[++rear] = bt->lchild;
            if (bt->rchild) que[++rear] = bt->rchild;
        }

        height++;
        levelCount = rear - front; // 下一层节点数
    }

    return height;
}

3. 按层分组输出叶子节点¶

C
void levelLeafByLayer(BiTree bt) {
    if (bt == NULL) return;

    BiTree que[maxsize];
    int front = 0, rear = 0;
    int levelCount = 1;

    que[++rear] = bt;

    while (front != rear) {
        printf("Level %d leaves: ", (rear - front) / levelCount);

        int currentLevelCount = levelCount;
        levelCount = 0;

        while (currentLevelCount > 0) {
            bt = que[++front];
            currentLevelCount--;

            if (!bt->lchild && !bt->rchild) {
                printf("%c ", bt->data);
            }

            if (bt->lchild) {
                que[++rear] = bt->lchild;
                levelCount++;
            }
            if (bt->rchild) {
                que[++rear] = bt->rchild;
                levelCount++;
            }
        }
        printf("\n");
    }
}

4. 使用 STL 队列的版本（C++）¶

C++
#include <queue>
void levelSTL(BiTree bt, int *n) {
    if (bt == NULL) return;

    std::queue<BiTree> que;
    que.push(bt);

    while (!que.empty()) {
        BiTree node = que.front();
        que.pop();

        if (!node->lchild && !node->rchild) {
            ++(*n);
        }

        if (node->lchild) que.push(node->lchild);
        if (node->rchild) que.push(node->rchild);
    }
}

5. 相关算法问题¶

统计每层叶子节点数：¶

C
void countLeavesByLevel(BiTree bt, int levelCounts[], int* maxLevel) {
    if (bt == NULL) return;

    BiTree que[maxsize];
    int front = 0, rear = 0;
    int currentLevel = 0;
    int nodesInCurrentLevel = 1;

    que[++rear] = bt;

    while (front != rear) {
        int nodesInNextLevel = 0;

        for (int i = 0; i < nodesInCurrentLevel; i++) {
            bt = que[++front];

            if (!bt->lchild && !bt->rchild) {
                levelCounts[currentLevel]++;
            }

            if (bt->lchild) {
                que[++rear] = bt->lchild;
                nodesInNextLevel++;
            }
            if (bt->rchild) {
                que[++rear] = bt->rchild;
                nodesInNextLevel++;
            }
        }

        currentLevel++;
        nodesInCurrentLevel = nodesInNextLevel;
    }

    *maxLevel = currentLevel;
}

6. 实际应用场景¶

文件系统统计：统计目录中文件（叶子）的数量
组织架构分析：统计没有下属的员工数量
网络拓扑：统计终端设备数量
游戏开发：统计决策树中的终端状态数
编译器：统计抽象语法树中的终结符数量

7. 性能优化技巧¶

C
// 提前终止优化：如果只需要知道是否有叶子节点
bool hasLeaf(BiTree bt) {
    if (bt == NULL) return false;

    BiTree que[maxsize];
    int front = 0, rear = 0;

    que[++rear] = bt;

    while (front != rear) {
        bt = que[++front];

        if (!bt->lchild && !bt->rchild) {
            return true; // 找到第一个叶子节点就返回
        }

        if (bt->lchild) que[++rear] = bt->lchild;
        if (bt->rchild) que[++rear] = bt->rchild;
    }

    return false;
}

这种方法体现了广度优先搜索（BFS）在树遍历中的应用，通过队列实现层次遍历，是解决树相关问题的经典方法。层次遍历特别适合处理需要按层处理或需要知道节点相对位置的问题。