《4》 编写函数int getWidth(BiTNode *T)，计算二叉树的最大宽度，并给出完整代码

以下是计算二叉树最大宽度的完整代码：

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

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

typedef struct QueueNode {
    BiTree data;
    struct QueueNode *next;
} QueueNode, *LinkQueuePtr;

typedef struct {
    LinkQueuePtr front;
    LinkQueuePtr rear;
} LinkQueue;

// 初始化队列
void InitQueue(LinkQueue *Q) {
    Q->front = Q->rear = (LinkQueuePtr) malloc(sizeof(QueueNode));
    if (!Q->front) {
        exit(-1);
    }
    Q->front->next = NULL;
}

// 判断队列是否为空
int QueueEmpty(LinkQueue Q) {
    return Q.front == Q.rear;
}

// 入队
void EnQueue(LinkQueue *Q, BiTree e) {
    LinkQueuePtr p = (LinkQueuePtr) malloc(sizeof(QueueNode));
    if (!p) {
        exit(-1);
    }
    p->data = e;
    p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;
}

// 出队
void DeQueue(LinkQueue *Q, BiTree *e) {
    if (Q->front == Q->rear) {
        return;
    }
    LinkQueuePtr p = Q->front->next;
    *e = p->data;
    Q->front->next = p->next;
    if (Q->rear == p) {
        Q->rear = Q->front;
    }
    free(p);
}

// 获取二叉树深度
int GetDepth(BiTree T) {
    if (!T) {
        return 0;
    }
    int left_depth = GetDepth(T->lchild);
    int right_depth = GetDepth(T->rchild);
    return (left_depth > right_depth ? left_depth : right_depth) + 1;
}

// 计算二叉树最大宽度
int getWidth(BiTree T) {
    if (!T) {
        return 0;
    }
    LinkQueue Q;
    InitQueue(&Q);
    EnQueue(&Q, T);
    int width = 1;
    while (!QueueEmpty(Q)) {
        int count = Q.rear - Q.front + 1;
        if (count > width) {
            width = count;
        }
        while (count--) {
            BiTree node;
            DeQueue(&Q, &node);
            if (node->lchild) {
                EnQueue(&Q, node->lchild);
            }
            if (node->rchild) {
                EnQueue(&Q, node->rchild);
            }
        }
    }
    return width;
}

int main() {
    // 构建二叉树
    BiTree A = (BiTree) malloc(sizeof(BiTNode));
    BiTree B = (BiTree) malloc(sizeof(BiTNode));
    BiTree C = (BiTree) malloc(sizeof(BiTNode));
    BiTree D = (BiTree) malloc(sizeof(BiTNode));
    BiTree E = (BiTree) malloc(sizeof(BiTNode));
    BiTree F = (BiTree) malloc(sizeof(BiTNode));
    A->data = 'A';
    B->data = 'B';
    C->data = 'C';
    D->data = 'D';
    E->data = 'E';
    F->data = 'F';
    A->lchild = B;
    A->rchild = C;
    B->lchild = D;
    B->rchild = NULL;
    C->lchild = E;
    C->rchild = F;
    D->lchild = D->rchild = NULL;
    E->lchild = E->rchild = NULL;
    F->lchild = F->rchild = NULL;

    // 测试计算二叉树最大宽度函数
    int width = getWidth(A);
    printf("The max width of the binary tree is: %d\n", width);

    return 0;
}

其中，我们使用了队列来辅助计算二叉树的最大宽度。具体来说，我们先将根节点入队，然后按层次遍历二叉树，每层统计节点个数并更新最大宽度值，然后将下一层的节点入队。最终返回的就是二叉树的最大宽度值。