学步园

#define TREELEN 5
struct NODE
{
	NODE* pLeft;
	NODE* pRight;
	char chValue;
};
void ReBuild(char* pPreOrder,char* pInOrder,int nTreeLen,NODE** pRoot)
{
	if(pPreOrder==NULL||pInOrder==NULL)
		return;
	NODE* pTemp=new NODE;
	pTemp->chValue=*pPreOrder;//获得前序遍历的第一个节点
	pTemp->pLeft=NULL;
	pTemp->pRight=NULL;
	if(*pRoot==NULL)
		*pRoot=pTemp;
	if(nTreeLen==1)
		return;//如果当前树的长度是1 ，直接返回
	//子树
	char* pOrgInOrder=pInOrder;
	char* pLeftEnd=pInOrder;//左子树末尾
	int nTempLen=0;
	//找到左子树末尾
	while(*pPreOrder!=*pLeftEnd)
	{
		if(pPreOrder==NULL||pLeftEnd==NULL)
			return;
		nTempLen++;
		if(nTempLen>nTreeLen)
			break;
		pLeftEnd++;
	}
	//左子树长度
	int nLeftLen=0;
	nLeftLen=(int)(pLeftEnd-pOrgInOrder);
	//右子树长度
	int nRightLen=0;
	nRightLen=nTreeLen-nLeftLen-1;
	if(nLeftLen>0)
		ReBuild(pPreOrder+1,pInOrder,nLeftLen,&((*pRoot)->pLeft));
	if(nRightLen>0)
		ReBuild(pPreOrder+nLeftLen+1,pInOrder+nLeftLen+1,nRightLen,&((*pRoot)->pRight));
}
void PreOrderTraverse(NODE* root)
{
	if(root)
	{
		cout<<root->chValue<<" ";
		PreOrderTraverse(root->pLeft);
		PreOrderTraverse(root->pRight);
	}
}
#define N 10000
void BFS(NODE* root)
{
	int top,rear;
	top=rear=0;
	NODE* queue[N];
	queue[rear++]=root;
	while(top<rear)//保证队列中有元素
	{
		NODE* q=queue[top++];
		cout<<q->chValue<<" ";
		if(q->pLeft!=NULL)
			queue[rear++]=q->pLeft;
		if(q->pRight!=NULL)
			queue[rear++]=q->pRight;
	}
}
int _tmain(int argc, _TCHAR* argv[])
{
	char p[]={'a','b','c','d','e'};
	char q[]={'c','b','d','a','e'};
	NODE* pRoot=NULL;
	ReBuild(p,q,TREELEN,&pRoot);
	PreOrderTraverse(pRoot);
	cout<<endl;
	BFS(pRoot);
	return 0;
}