算法与数据结C语言计算二叉树的最大宽度

同样可以使用层次遍历的思想来计算二叉树的最大宽度。下面是 C 语言实现：

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点的结构体
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 定义队列的结构体
typedef struct Queue {
    TreeNode **data;
    int head;
    int tail;
    int size;
} Queue;

// 初始化队列
void initQueue(Queue *q, int size) {
    q->data = (TreeNode **)malloc(sizeof(TreeNode *) * size);
    q->head = 0;
    q->tail = 0;
    q->size = size;
}

// 判断队列是否为空
int isEmpty(Queue *q) {
    return q->head == q->tail;
}

// 将节点入队
void enqueue(Queue *q, TreeNode *node) {
    q->data[q->tail++] = node;
}

// 将节点出队
TreeNode *dequeue(Queue *q) {
    return q->data[q->head++];
}

// 计算二叉树的最大宽度
int maxWidth(TreeNode *root) {
    if (!root) {
        return 0;
    }
    
    Queue q;
    initQueue(&q, 1000);  // 假设二叉树节点数不超过 1000
    
    enqueue(&q, root);
    int maxWidth = 1;
    
    while (!isEmpty(&q)) {
        int levelWidth = q.tail - q.head;
        
        for (int i = 0; i < levelWidth; i++) {
            TreeNode *node = dequeue(&q);
            
            if (node->left) {
                enqueue(&q, node->left);
            }
            if (node->right) {
                enqueue(&q, node->right);
            }
        }
        
        if (q.tail - q.head > 0) {
            maxWidth = q.tail - q.head > maxWidth ? q.tail - q.head : maxWidth;
        }
    }
    
    return maxWidth;
}

int main() {
    // 构造如下的二叉树
    //     1
    //    / \
    //   2   3
    //  / \   \
    // 4   5   6
    TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    TreeNode *node2 = (TreeNode *)malloc(sizeof(TreeNode));
    TreeNode *node3 = (TreeNode *)malloc(sizeof(TreeNode));
    TreeNode *node4 = (TreeNode *)malloc(sizeof(TreeNode));
    TreeNode *node5 = (TreeNode *)malloc(sizeof(TreeNode));
    TreeNode *node6 = (TreeNode *)malloc(sizeof(TreeNode));
    
    root->val = 1;
    node2->val = 2;
    node3->val = 3;
    node4->val = 4;
    node5->val = 5;
    node6->val = 6;
    
    root->left = node2;
    root->right = node3;
    node2->left = node4;
    node2->right = node5;
    node3->right = node6;
    node4->left = node4->right = NULL;
    node5->left = node5->right = NULL;
    node6->left = node6->right = NULL;
    
    printf("%d\n", maxWidth(root));  // 输出 2
    
    return 0;
}

其中，`TreeNode` 是二叉树节点的结构体，`Queue` 是队列的结构体。`initQueue`、`isEmpty`、`enqueue` 和 `dequeue` 分别是队列的初始化、判断队列是否为空、将节点入队和将节点出队的函数。`maxWidth` 是计算最大宽度的函数。该函数的时间复杂度为 $O(n)$，其中 $n$ 是二叉树的节点数。