前シーケンスと中シーケンスの遍歴シーケンスに基づいてツリーコードの完全版を再構築
タイトル前順と中順遍歴シーケンスに基づいて二叉木を再構築する
前シーケンスループ結果abdcefを入力すると
中系遍歴結果dbaecf
ツリーを再構築し、後続の遍歴シーケンスbdcefaを出力する
前シーケンスループ結果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;
}