【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：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);