#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?	{
		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?			{
				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