PTA（树和二叉树）1-8 最宽层次结点数

1-8 最宽层次结点数

分数 4

作者 DS课程组

单位 临沂大学

本题要求实现一个函数，返回给定的二叉树的中最宽层次的结点数，这里最宽层次指的是该层上的结点最多。

函数接口定义：

1
int MaxWidth(BiTree T);

T是二叉树树根指针，MaxWidth函数统计T中每层结点数并返回最大值，空树返回0。

其中BinTree结构定义如下：

1
2
3
4
5
6
typedef char ElemType;
typedef struct BiTNode
{
   ElemType data;
   struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

裁判测试程序样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;
typedef struct BiTNode
{
   ElemType data;
   struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

BiTree Create();/* 细节在此不表 */

int MaxWidth(BiTree T);

int main()
{
   BiTree T = Create();
   printf("The max-width of the tree is %d.\n",MaxWidth(T)); 
   return 0;
}
/* 你的代码将被嵌在这里 */

输入样例：

输入为由字母和’#’组成的字符串，代表二叉树的扩展先序序列。例如对于如下二叉树，输入数据：

1
AB#DF##G##C##

输出样例（对于图中给出的树）：

二叉树.png

1
The max-width of the tree is 2.

答案

  • 这题跟1-6遍历一样的（只是多了一个统计一层中最大结点数）

  • 因为编译器给的是C，所以队列要自己实现

  • 逻辑太妙了，值得反复品味

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// 定义队列结点结构
typedef struct QueueNode {
    BiTree data;
    struct QueueNode *next;
} QueueNode;
// 定义队列结构
typedef struct {
    QueueNode *front;
    QueueNode *rear;
} Queue;

// 初始化队列
Queue* CreateQueue() {
    Queue *queue = (Queue*) malloc(sizeof (Queue));
    queue->front = queue->rear = NULL;
    return queue;
}

// 入队
void EnQueue(Queue *q, BiTree node) {
    QueueNode *newNode = (QueueNode*) malloc(sizeof (QueueNode));
    newNode->data = node;
    newNode->next = NULL;
    if (q->rear == NULL) { // 队列为空时，队头和队尾都指向新节点
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

// 出队操作
BiTree DeQueue(Queue *q) {
    if (q->front == NULL) return NULL; // 队列为空
    QueueNode *temp = q->front;
    BiTree node = temp->data;
    q->front = q->front->next;
    if (q->front == NULL) { // 若队头为空，队尾也置空
        q->rear = NULL;
    }
    free(temp);
    return node;
}

// 检查队列是否为空
int IsEmpty(Queue *q) {
    return q->front == NULL;
}

int MaxWidth(BiTree T){
    if (T == NULL) return 0; // 空树返回0

    int current_max = 0;
    int global_max = 0;
    Queue *queue = CreateQueue();
    EnQueue(queue, T); // 先将树根结点入队

    while (!IsEmpty(queue)) {
        current_max = 0;
        QueueNode *current = queue->front;

        // 统计当前层的结点数
        while (current != NULL) {
            current_max++;
            current = current->next;
        }

        // 更新最大宽度
        if (current_max > global_max) {
            global_max = current_max;
        }

        // 当前层的所有结点出队，并将他们的子节点入队
        for (int i = 0; i < current_max; ++i) {
            BiTree node = DeQueue(queue); // 删除队列queue中的结点，并返回该节点的指针
            if (node->lchild != NULL) {
                EnQueue(queue, node->lchild);
            }
            if (node->rchild != NULL) {
                EnQueue(queue, node->rchild);
            }
        }
    }
    return global_max;
}

用层次遍历 + 队列统计每层节点数，跟踪最大值。

1. 核心思路

  • 用队列存储二叉树节点，按层次依次入队 / 出队。
  • 每处理一层前，先统计当前队列长度（即该层节点数）。
  • 对比更新最大节点数，再将当前层节点的非空子节点入队，循环至所有层处理完。

2. 步骤拆解

  1. 空树直接返回 0，避免无效操作。
  2. 初始化队列，将根节点入队，准备开始层次遍历。
  3. 循环处理队列（队列非空时）：
    • 统计当前队列长度 → 得到当前层节点数。
    • 若当前层节点数更大，更新全局最大值。
    • 出队当前层所有节点，将它们的非空左右子节点入队（为下一层统计做准备）。
  4. 循环结束，返回全局最大节点数（最宽层次的结点数）。