二叉木の幅C実装(非再帰)

階層遍歴方式を採用し、1つのキューを使用して、各層のノードが順次入隊し、出隊し、幅を統計し、この層幅と前のk層の最大幅の大きさを比較する.

typedef int DataType;
struct Node
{
    DataType data;
    struct Node *leftChild;
    struct Node *rightChild;
};
typedef struct Node BiTreeNode,*BiTree;

typedef struct QNode
{
    BiTreeNode *addr;
    struct QNode *link;
}qnode;

int Width_T(BiTree T)
{
    /*      ，        0，               
     *          ，                
     *    ：           ，      ，        k        
     */
    int parentsize,currentsize,maxsize;
    parentsize = currentsize = maxsize = 0;
    if(T == NULL)
        return 0;
    qnode *head,*rear,*p,*q;//      
    head = rear = NULL;
    p = (qnode*)malloc(sizeof(qnode));
    p->addr = T;
    p->link = NULL;
    head = p;//     
    rear = p;
    parentsize = maxsize= 1;
    int i;
    while(head!= NULL)
    {
        currentsize = 0;
        i = 0;
        while(i < parentsize && head != NULL)//    ，      
        {
            if(head != NULL)
            {
                if(head->addr->leftChild != NULL)
                {
                    p = (qnode*)malloc(sizeof(qnode));
                    p->addr = head->addr->leftChild;
                    p->link = NULL;
                    rear->link = p;
                    rear = p;
                    currentsize++;
                }
                if(head->addr->rightChild != NULL)
                {
                    p = (qnode*)malloc(sizeof(qnode));
                    p->addr = head->addr->rightChild;
                    p->link = NULL;
                    rear->link = p;
                    rear = p;
                    currentsize++;
                }
            }
            q = head;
            head = head->link;
            free(q);
            i++;
        }
        if(maxsize < currentsize)
            maxsize = currentsize;
        parentsize = currentsize;
    }
    return maxsize;
}