计算二叉树的最大宽度

求非空二叉树的宽度

算法思想：层序遍历二叉树，并用两个队列A,B交替存储结点，当队列A中元素为空时队列B就存储了下一层的所有结点，同理，队列B为空时队列A也就存储了下一层的所有结点。记录每层的最大宽度并与当前最大宽度比较并更新最大宽度，遍历完所有结点后即可求出最大宽度。

int BTWidth(BiTree bt){
    int max=0,num=0;
    InitQueue(A); InitQueue(B);          //初始化A B两队列
    EnQueue(A,bt); max++;                //先让根节点入队，并让max=1
    BiTree p;                            //定义p指针用来出队或入队
    while(!IsEmpty(A)||!IsEmpty(B)){     //当两个队列都为空时结束循环
        while(!IsEmpty(A)){              //A出队，记录B中的宽度
            num=0;
            DeQueue(A,p)                 //让A的对头出队并用p指向他
            if(p->lchild){               //若有左孩子，则左孩子进入队B
                EnQueue(B,p->lchild);   
                num++;
            }    
            if(p->rchild){               //若有右孩子，则右孩子进入队B
                EnQueue(B,p->rchild);
                num++;
            }
        }
        max=(max>num)?max:num;       //更新最大宽度(与B中宽度比较)
        while(!IsEmpty(B)){              //B出队，记录A中的宽度
            num=0;
            DeQueue(B,p)                 
            if(p->lchild){               //若有左孩子，则左孩子进入队A
                EnQueue(A,p->lchild);
                num++;
            }
            if(p->rchild){               //若有右孩子，则右孩子进入队A
                EnQueue(A,p->rchild);
                num++;
            }
        }
        max=(max>num)?max:num;       //更新最大宽度(与A中宽度比较)
    }
    return max;
}