前シーケンスと中シーケンスの遍歴シーケンスに基づいてツリーコードの完全版を再構築

2272 ワード

タイトル前順と中順遍歴シーケンスに基づいて二叉木を再構築する
前シーケンスループ結果abdcefを入力すると
中系遍歴結果dbaecf
ツリーを再構築し、後続の遍歴シーケンスbdcefaを出力する
 
 
#include <iostream>
using namespace std;

struct Node{
	Node* pLeft;
	Node* pRight;
	char chValue;
};

 Node* build(char*pPreOrder, int preLeft,int preRight,char* pInOrder, int inLeft,int inRight)
{

	Node *pRoot = new Node;
	pRoot->chValue  = pPreOrder[preLeft];

	int i;
	for(i=inLeft;i<=inRight;i++)
		if(pInOrder[i]==pPreOrder[preLeft])
			break;

	int leftCount = i-inLeft;
	int rightCount = inRight - i;

	if(leftCount==0) pRoot->pLeft=NULL;
	else pRoot->pLeft=build(pPreOrder, preLeft+1,preLeft+leftCount,pInOrder, inLeft,i-1);


	if(rightCount==0) pRoot->pRight=NULL;
	else pRoot->pRight=build(pPreOrder, preLeft+leftCount+1,preRight,pInOrder,i+1,inRight);

	return pRoot;
}


void rebuild(char* pPreOrder, char* pInOrder, int nTreeLen, Node** pRoot)
{
	*pRoot = build(pPreOrder,0,nTreeLen-1,pInOrder,0,nTreeLen-1);
}


//just for test
void preTraverse(Node* head)
{
	if(head==NULL) return;

	cout<<head->chValue;
	preTraverse(head->pLeft);
	preTraverse(head->pRight);

}

//just for test
void inTraverse(Node* head)
{
	if(head==NULL) return;

	preTraverse(head->pLeft);
	cout<<head->chValue;
	preTraverse(head->pRight);

}

//just for test
void postTraverse(Node* head)
{
	if(head==NULL) return;

	preTraverse(head->pLeft);
	preTraverse(head->pRight);
	cout<<head->chValue;
}

int main()
{
	//just for test
	char pPreOrder[] = "abdcef";
	char pInOrder[] = "dbaecf";
	Node* head = NULL;

	rebuild(pPreOrder,pInOrder,6,&head);

	preTraverse(head);
	cout<<endl;
	inTraverse(head);
	cout<<endl;
	postTraverse(head);
	cout<<endl;
	return 0;

}