分层建立多叉树及分层遍历输出

#include “StdAfx.h“
#include “MyTree.h“
#define  MAX_CENG_SIZE	10		//允许最大层数
#define  MAX_NODE_SIZE	3		//允许最大节点数
#define  MAX_BUF_SIZE	20		//允许申请最大内存空间
#define	 MAX_VALUE_SIZE	1000	//允许节点值的最大值

CMyTree::CMyTree（void）
{
	m_pTreeRoot = NULL;
}

CMyTree::~CMyTree（void）
{
	DeleteTree（）;
}

int CMyTree::DeleteTree（）
{
	if （!m_pTreeRoot）
		return 0;
	/////////////////////
	//应用队列遍历多叉树依次删除
	queue queueTree;
	queueTree.push（m_pTreeRoot）;
	CTreeNode* pNode = NULL;
	while （!queueTree.empty（））
	{
		pNode = queueTree.front（）;
		queueTree.pop（）;
		if （pNode->IsLeaf（））		//删除叶子节点
		{
			if （!pNode->IsRoot（））
			{
				CTreeNode* pNodeParents = pNode->GetParents（）;
				pNodeParents->DeleteChildrenNode（pNode）;  //首先断开和父节点的链接
			}			
			delete pNode;
			continue;
		}
		list* treeNodeList = pNode->GetChildrenList（）;
		list::iterator ite;
		for （ite = treeNodeList->begin（）; ite != treeNodeList->end（）; ite++）
		{
			queueTree.push（*ite）;
		}
	}

	m_pTreeRoot = NULL;
	return 0;
}

int CMyTree::CreatTree（）
{
	if （m_pTreeRoot）
	{
		DeleteTree（）;
	}
	m_pTreeRoot = new CTreeNode（）;
	

	/////////////////////////////
	//应用2个队列分层创建树
	queue queueTree1;
	queue queueTree2;
	queueTree1.push（m_pTreeRoot）;

	srand（（unsigned）time（NULL））;

	int nValue = rand（）%MAX_VALUE_SIZE;		
	int nBufSize = rand（）%MAX_BUF_SIZE;
	/////////////////////////////
	//根节点设置数值及申请内存
	m_pTreeRoot->SetNodeValue（nValue）;
	m_pTreeRoot->SetBufSize（nBufSize）;

	int nHeight = rand（）%MAX_CENG_SIZE;	//层数
	for （int i = 0; i < nHeight-1; i++）
	{
		queue *pTempQueuePush = NULL;
		queue *pTempQueuePop = NULL;
		if （0 == i%2）
		{
			pTempQueuePop = &queueTree1;
			pTempQueuePush = &queueTree2;
		}
		else
		{
			pTempQueuePop = &queueTree2;
			pTempQueuePush = &queueTree1;
		}
		while （!pTempQueuePop->empty（））
		{
			CTreeNode* pTreeNode = pTempQueuePop->front（）;
			pTempQueuePop->pop（）;

			/////////////////////////////
			//添加子节点
			int nChildrenNum = rand（）%MAX_NODE_SIZE;
			nChildrenNum = nChildrenNum == 0 ? 1 : nChildrenNum;
			for （int j = 0; j < nChildrenNum; j++）
			{
				CTreeNode* pChildrenNode = new CTreeNode（）;
				int nValue = rand（）%MAX_VALUE_SIZE;		
				int nBufSize = rand（）%MAX_BUF_SIZE;
				/////////////////////////////
				//设置数值及申请内存
				pChildrenNode->SetNodeValue（nValue）;
				pChildrenNode->SetBufSize（nBufSize）;

				pTreeNode->InsertChildrenNode（pChildrenNode）;
				pTempQueuePush->push（pChildrenNode）;	//记录当前层的节点
			}			
		}
	}
	return 0;
}


int CMyTree::PrintTree（）
{
	if （!m_pTreeRoot）
		return 0;
	stack stackTree;   // 保存树节点栈
	map	mapCengSize;	//记录栈中每层的节点数
	int nCengNum = 0;				//记录当前层数
	mapCengSize.insert（map::value_type（0 1））;
	stackTree.push（m_pTreeRoot）;
	while（!stackTree.empty（））
	{
		CTreeNode* pNode = stackTree.top（）;
		stackTree.pop（）;
		map