#include<stdio.h>
#include<stdlib.h>
//定义二叉树
typedef struct BiNode{
int data;
struct BiNode *lchild,*rchild;
}BiNode,*BiTree;
//创建二叉树
void CreateBiTree(BiTree T){
int a;
scanf("%d",&a);
if(a==0)
T=NULL;
else{
T=(BiTree)malloc(sizeof(BiNode));
T->data=a;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
//定义队列
typedef struct Qnode{
BiTree data;
struct Qnode *next;
}Qnode,*QuenePtr;
typedef struct{
QuenePtr front;
QuenePtr rear;
}LinkQueue;
//队列初始化
void InitQueue(LinkQueue &Q){
Q.front=Q.rear=(QuenePtr)malloc(sizeof(Qnode));
Q.front->next=NULL;
}
//入队
void EnQueue(LinkQueue &Q,BiTree T){
QuenePtr p;
p=(QuenePtr)malloc(sizeof(Qnode));
p->data=T;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
}
//出队
void DeQueue(LinkQueue &Q){
QuenePtr p;
if(Q.front!=Q.rear){
p=Q.front;
Q.front->next=p->next;
free(p);
}
}
//求队列长度
int length(LinkQueue &Q){
int len=0;
QuenePtr p;
p=Q.front->next;
while(p){
len++;
p=p->next;
}
return len;
}
//求二叉树宽度
int maxwidth(BiTree T){
int len,width=0;
LinkQueue Q;
InitQueue(Q);
QuenePtr p;
BiTree T1;
p=(QuenePtr)malloc(sizeof(Qnode));
InitQueue(Q);
if(T->lchild){
EnQueue(Q,T->lchild);
}
if(T->rchild){
EnQueue(Q,T->rchild);
}
width=len=length(Q);
p=Q.front;
while(p){
T1=p->data;
if(T1->lchild){
EnQueue(Q,T1->lchild);
}
if(T1->rchild){
EnQueue(Q,T1->rchild);
}
DeQueue(Q);
len--;
if(len==0){
len=length(Q);
width=width>len?width:len;
}
p=Q.front;
}
return width;
}
//主函数
int main(){
int width;
BiTree T;
CreateBiTree(T);
width=maxwidth(T);
printf("%d",width);
return 0;
}