在二叉樹的遍歷當(dāng)中，有一種遍歷方法是不常見的，那就是廣度遍歷。和其他三種遍歷方法不同，二叉樹的廣度遍歷需要額外的數(shù)據(jù)結(jié)構(gòu)來幫助一下？什么數(shù)據(jù)結(jié)構(gòu)呢？那就是隊列。因為隊列具有先進先出的特點，這個特點要求我們在遍歷新的一層數(shù)據(jù)之前，必須對上一次的數(shù)據(jù)全部遍歷結(jié)束。暫時還沒有掌握隊列知識的朋友可以看一看我的這一篇博客—[隊列][1]。

a）下面是新添加的隊列數(shù)據(jù)結(jié)構(gòu)，其中數(shù)據(jù)部分換成了樹節(jié)點指針的指針：

typedef struct _QUEUE
{
    int head;
    int tail;
    int length;
    TREE_NODE** pHead;
}QUEUE;

注：head表示開始，tail表示結(jié)束，length表示pHead的長度，pHead表示指針的起始地址

b）創(chuàng)建隊列，因為涉及到length的長度問題，所以需要計算二叉樹中節(jié)點的總數(shù)

QUEUE* create_queue_for_tree(const TREE_NODE* pTreeNode)
{
    QUEUE* pQueue;
    int count;

    if(NULL == pTreeNode)
        return NULL;

    count = count_all_node_number(pTreeNode);
    pQueue = (QUEUE*)malloc(sizeof(QUEUE));
    assert(NULL != pQueue);
    memset(pQueue, 0, sizeof(QUEUE));

    pQueue->pHead = (TREE_NODE**)malloc(sizeof(TREE_NODE*)* count);
    assert(NULL != pQueue->pHead);
    memset(pQueue->pHead, 0, sizeof(TREE_NODE*) * count);

    pQueue->head = pQueue->tail = 0;
    pQueue->length = count;
    return pQueue;
}

c）實現(xiàn)隊列的數(shù)據(jù)加入和數(shù)據(jù)彈出操作

void insert_node_into_queue(QUEUE* pQueue, TREE_NODE* pNode)
{
    if(NULL == pQueue || NULL == pQueue->pHead ||NULL == pNode)
        return;

    pQueue->pHead[pQueue->tail ++] = pNode;
    return;
}

TREE_NODE* get_node_from_queue(QUEUE* pQueue)
{
    if(NULL == pQueue || NULL == pQueue->pHead)
        return NULL;

    if(pQueue->head == pQueue->tail)
        return NULL;

    return pQueue->pHead[pQueue->head++];
}

注：這里定義的隊列不是循環(huán)隊列，所以數(shù)據(jù)的壓入和彈出比較簡單，直接對head和tail處理即可

d）遍歷節(jié)點，按層得到數(shù)據(jù)，最后再pQueue->pHead中得到的指針數(shù)據(jù)就是按層輸出的結(jié)果

QUEUE* traverse_node_by_layer(TREE_NODE* pNode)
{
    QUEUE* pQueue;
    if(NULL ==pNode)
        return NULL;

    pQueue = create_queue_for_tree(pNode);
    assert(NULL != pQueue);

    /* 首個節(jié)點加入隊列 */
    insert_node_into_queue(pQueue, pNode);
    pNode = get_node_from_queue(pQueue);

    while(pNode){
        if(pNode->left)
            insert_node_into_queue(pQueue, pNode->left);

        if(pNode->right)
            insert_node_into_queue(pQueue, pNode->right);

        pNode = get_node_from_queue(pQueue);
    }

    return pQueue;
}

擴充部分：

上面的辦法已經(jīng)可以實現(xiàn)隊列的按層輸出，那么如果想在節(jié)點結(jié)構(gòu)中直接實現(xiàn)數(shù)據(jù)的按層訪問怎么辦？其實兩步走就可以：1）在已有的TREE_NODE添加prev和next；（2）按照剛才得到的pQueue->pHead結(jié)果，依次對prev和next進行賦值即可。不知道朋友們明白了沒？