题目:(微软)
输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印。
例如输入:
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;
}