C++算法之二叉樹廣度遍歷

在二叉樹的遍歷當中，有一種遍歷方法是不常見的，那就是廣度遍歷。和其他三種遍歷方法不同，二叉樹的廣度遍歷需要額外的數據結構來幫助一下？什么數據結構 呢？那就是隊列。因為隊列具有先進先出的特點，這個特點要求我們在遍歷新的一層數據之前，必須對上一次的數據全部遍歷結束。     a）下面是新添加的隊列數據結構，其中數據部分換成了樹節點指針的指針：

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

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;  

}
</pre>     c）實現隊列的數據加入和數據彈出操作
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++];  

}

</pre>     注：這里定義的隊列不是循環隊列，所以數據的壓入和彈出比較簡單，直接對head和tail處理即可

 

     d）遍歷節點，按層得到數據，最后再pQueue->pHead中得到的指針數據就是按層輸出的結果
QUEUE traverse_node_by_layer(TREE_NODE pNode)

{

    QUEUE* pQueue;

    if(NULL ==pNode)

        return NULL;


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

/* 首個節點加入隊列 */  
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;  

}
</pre> 擴充部分：

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