【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：feixiaoxing @163.com】
在二叉樹的遍歷當中，有一種遍歷方法是不常見的，那就是廣度遍歷。和其他三種遍歷方法不同，二叉樹的廣度遍歷需要額外的數據結構來幫助一下？什麼數據結構呢？那就是隊列。因為隊列具有先進先出的特點，這個特點要求我們在遍歷新的一層數據之前，必須對上一次的數據全部遍歷結束。暫時還沒有掌握隊列知識的朋友可以看一看我的這一篇博客—隊列。
a）下面是新添加的隊列數據結構，其中數據部分換成了樹節點指針的指針：
typedef struct _QUEUE
{
int head;
int tail;
int length;
TREE_NODE** pHead;
}QUEUE;
typedef struct _QUEUE
{
int head;
int tail;
int length;
TREE_NODE** pHead;
}QUEUE; 注：head表示開始，tail表示結束，length表示pHead的長度，pHead表示指針的起始地址
b）創建隊列，因為涉及到length的長度問題，所以需要計算二叉樹中節點的總數
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;
}
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）實現隊列的數據加入和數據彈出操作
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++];
}
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++];
} 注：這裡定義的隊列不是循環隊列，所以數據的壓入和彈出比較簡單，直接對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;
}
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;
}
擴充部分：
上面的辦法已經可以實現隊列的按層輸出，那麼如果想在節點結構中直接實現數據的按層訪問怎麼辦？其實兩步走就可以：1）在已有的TREE_NODE添加prev和next；（2）按照剛才得到的pQueue->pHead結果，依次對prev和next進行賦值即可。不知道朋友們明白了沒？
