自留地

void PreTravel(TreeNode *pRoot)
{
	if (pRoot == NULL)
		return;
    stack<TreeNode*> nodeStack;
	nodeStack.push(pRoot);
	cout<<"preTravel:"<<endl;
	while (!nodeStack.empty())
	{
		TreeNode *pNode = nodeStack.top();
		nodeStack.pop();
		cout<<pNode->data<<' ';
		if (pNode->pRight != NULL)
		{
			nodeStack.push(pNode->pRight);
		}
		if (pNode->pLeft != NULL)
		{
			nodeStack.push(pNode->pLeft);
		}
	}
	cout<<endl<<endl;

}

void midTravel(TreeNode *pRoot)
{
	if (pRoot == NULL)
		return;
	stack<TreeNode*> nodeStack;
	TreeNode *pNode = pRoot;
	cout<<"midTravel:"<<endl;
	while (pNode != NULL || !nodeStack.empty())
	{
		if (pNode != NULL)
		{
			nodeStack.push(pNode);
			pNode = pNode->pLeft;
		} 
		else
		{
			pNode = nodeStack.top();
			cout<<pNode->data<<' ';
			nodeStack.pop();
			pNode = pNode->pRight;
		}
	}
	cout<<endl<<endl;
}

void postTravel(TreeNode *pRoot)
{
	if (pRoot == NULL)
		return;
	stack<TreeNode*> nodeStack;
	TreeNode *pNode = pRoot;
	cout<<"postTravel:"<<endl;
	while (pNode != NULL || !nodeStack.empty())
	{
		if (pNode != NULL)
		{
			nodeStack.push(pNode);
			pNode = pNode->pLeft;
		} 
		else
		{
			pNode = nodeStack.top();
			nodeStack.pop();
			if (!pNode->visited)
			{
				pNode->visited = true;
				nodeStack.push(pNode);
				pNode = pNode->pRight;
			} 
			else
			{
				cout<<pNode->data<<' ';
				pNode = NULL;
			}
		}
	}
	cout<<endl<<endl;
}

void layerTravel(TreeNode *pRoot)
{
        if (pRoot == NULL)
		return;
	deque<TreeNode*> nodeDeque;
	nodeDeque.push_back(pRoot);
	cout<<"layerTravel:"<<endl;
	while (!nodeDeque.empty())
	{
		TreeNode *pNode = nodeDeque.front();
		nodeDeque.pop_front();
		cout<<pNode->data<<' ';
		if (pNode->pLeft != NULL)
			nodeDeque.push_back(pNode->pLeft);
		if (pNode->pRight != NULL)
			nodeDeque.push_back(pNode->pRight);
	}
	cout<<endl<<endl;
}

void ConstructTree(int* preSeq, int* midSeq, int treeLen, TreeNode **ppRoot)
{
	if (NULL == preSeq || NULL == midSeq || treeLen <= 0)
		return;
	int nRoot = *preSeq;
	TreeNode *pNode = new TreeNode(nRoot, false, NULL, NULL);
	if(NULL == *ppRoot)
		*ppRoot = pNode;
	int nPos = -1;
	for (int i=0; i<treeLen; ++i)
	{
		if (midSeq[i] == nRoot)
		{
			nPos = i;
			break;
		}
	}
	if (nPos >= treeLen || nPos < 0)
		return;
	ConstructTree(preSeq+1, midSeq, nPos, &pNode->pLeft);
	ConstructTree(preSeq+nPos+1, midSeq+nPos+1, treeLen-nPos-1, &pNode->pRight);

}

void DestroyTree(TreeNode *pRoot)
{
	if (pRoot == NULL)
		return;
	if (pRoot->pLeft != NULL)
	{
		DestroyTree(pRoot->pLeft);
		pRoot->pLeft = NULL;
	}
	if (pRoot->pRight != NULL)
	{
		DestroyTree(pRoot->pRight);
		pRoot->pRight = NULL;
	}
	cout<<"data "<<pRoot->data<<" has been deleted."<<endl;
	delete pRoot;
	pRoot = NULL;
}