每天學習一算法系列（16）(輸入一顆二進制樹，從上往下按層列印樹的每個結點，同一層中按照從左往右的順序列印)

題目：（微軟）

輸入一顆二進制樹，從上往下按層列印樹的每個結點，同一層中按照從左往右的順序列印。

例如輸入：

    8

   / \

  6  10

 / \   / \

5 7 9 11

輸出：8 6 10 5 7 9 11.

思路一：

這道題目其實就是二叉樹的層次周遊的問題，借用隊列來解。

具體思路是：從根節點開始，先把根節點入隊列，然後一直往隊列取出節點，并通路節點值，如果節點的左子樹，右子樹不為空就把該節點入隊列。

代碼如下：

#include "stdafx.h"
#include "Queue.h"
#include <assert.h>

/*--------------------------------
層次周遊二叉樹.
Copyright by yuucyf.	 2011.07.20
----------------------------------*/

void AddBSTreeNode(S_BSTreeNode* &psRoot, int nValue)
{
	if (NULL == psRoot)
	{
		psRoot = new S_BSTreeNode;
		assert(NULL != psRoot);
		psRoot->nValue = nValue;
		return;
	}

	if (psRoot->nValue > nValue)
	{
		AddBSTreeNode(psRoot->psLeft, nValue);
	}
	else if (psRoot->nValue < nValue)
	{
		AddBSTreeNode(psRoot->psRight, nValue);
	}
}

void VisitByLevel(S_BSTreeNode* psRoot)
{
	if (NULL == psRoot)
		return;

	C_Queue<S_BSTreeNode *> queueNode;
	queueNode.QInsert(psRoot);

	S_BSTreeNode *pCurNode = NULL;
	while (!queueNode.QEmpty())
	{
		pCurNode = queueNode.QDelete();
		assert(NULL != pCurNode);
		_tprintf(_T("%d "), pCurNode->nValue);

		if (pCurNode->psLeft)
			queueNode.QInsert(pCurNode->psLeft);
		if (pCurNode->psRight)
			queueNode.QInsert(pCurNode->psRight);
	}
}


int _tmain(int argc, _TCHAR* argv[])
{
	S_BSTreeNode *psRoot = NULL;
	AddBSTreeNode(psRoot, 8);
	AddBSTreeNode(psRoot, 6);
	AddBSTreeNode(psRoot, 10);
	AddBSTreeNode(psRoot, 5);
	AddBSTreeNode(psRoot, 7);
	AddBSTreeNode(psRoot, 9);
	AddBSTreeNode(psRoot, 11);

	VisitByLevel(psRoot);
	return 0;
}