二叉树的层次遍历

思路：二叉树的层次遍历思路，借助队列来实现。相当于广度优先搜索，使用队列（深度优先搜索的话，使用栈）。

 若根节点为空，直接返回；
 若根节点非空，则将根节点入队，然后，判断队列是否为空，若不为空，则将队首节点出队，访问，

 并判断其左右子节点是否为空，若不为空，则压入队列。

步骤：

1.申请一个辅助队列，并且先把根节点入队

2.判断队列是否为空

3.队列不为空则进入循环，循环条件就是队列是否为空

4.循环内：弹出队列的结点，并且打印结点中的内容，如果结点的左子树或右子树不为空，则入队

代码：

typedef struct node
{
	int nValue;
	struct node *pLeft;
	struct node *pRight;
}BinaryTree;

typedef struct node3
{
	BinaryTree* nValue;
	struct node3 *pNext;
}MyQueue;

typedef struct node4
{
	int nCount;
	MyQueue *pHead;
	MyQueue *pTail;
}Queue;

void q_Init(Queue **pQueue)
{
	*pQueue = (Queue*)malloc(sizeof(Queue));
	(*pQueue)->pHead = NULL;
	(*pQueue)->pTail = NULL;
	(*pQueue)->nCount = 0;
}

void q_Push(Queue *pQueue,BinaryTree* nNum)
{
	if(pQueue == NULL)return;

	MyQueue *pTemp = NULL;
	pTemp = (MyQueue*)malloc(sizeof(MyQueue));
	pTemp->nValue = nNum;
	pTemp->pNext = NULL;

	if(pQueue->pHead == NULL)
	{
		pQueue->pHead = pTemp;
	}
	else
	{
		pQueue->pTail->pNext = pTemp;
	}
	pQueue->pTail = pTemp;
	pQueue->nCount++;
}

BinaryTree* q_Pop(Queue *pQueue)
{
	if(pQueue == NULL || pQueue->nCount == 0)return NULL;

	MyQueue *pDel = NULL;
	BinaryTree* nNum = NULL;
	pDel = pQueue->pHead;
	nNum = pDel->nValue;

	pQueue->pHead = pQueue->pHead->pNext;
	free(pDel);
	pDel = NULL;

	pQueue->nCount--;
	if(pQueue->nCount == 0)
	{
		pQueue->pTail = NULL;
	}
	return nNum;
}

int q_IsEmpty(Queue *pQueue)
{
	if(pQueue == NULL)return -1;
	return pQueue->nCount ? 0:1;
}

//层次遍历函数

void LevelTraversal(BinaryTree *pTree)
{
	if(pTree == NULL)return;

	//申请辅助队列
	Queue *pQueue = NULL;
	q_Init(&pQueue);

	//根入队
	q_Push(pQueue,pTree);

	while(!q_IsEmpty(pQueue))
	{
		//弹出
		pTree = q_Pop(pQueue);

		//打印
		printf("%d ",pTree->nValue);

		//非空左右入队
		if(pTree->pLeft != NULL)
		{
			q_Push(pQueue,pTree->pLeft);
		}

		if(pTree->pRight != NULL)
		{
			q_Push(pQueue,pTree->pRight);
		}
	}
}