由先序遍历和中序遍历回复树结构
动态规划法，找到左子树和右子树解即为整个树的解#include <iostream>
using namespace std;
#define min(x,y) ((x<y)?x:y)
#define arr(x,y) arr[(x)*size2+(y)]
struct NODE
{
NODE* pLeft;
NODE* pRight;
char chValue;
};
NODE* tranverse(char* pre,int preb,int pree,char* in,int inb,int ine)
{
NODE* father=new NODE();
father->chValue=pre;
int i=inb;
for(;i<=ine;i++)
{
if(in == pre)
break;
}
father->pLeft=NULL;
father->pRight=NULL;
int l1=i-inb,l2=ine-i;//pre=>inpre=>in
if(l1>0)
{
father->pLeft=tranverse(pre,preb+1,preb+l1,in,inb,inb+l1-1);
}
if(l2>0)
{
father->pRight=tranverse(pre,pree-l2+1,pree,in,ine-l2+1,ine);
}
return father;
}
void Rebuild(char* pPreOrder,char* InOrder,int nTreeLen,NODE** pRoot)
{
*pRoot=tranverse(pPreOrder,0,nTreeLen-1,InOrder,0,nTreeLen-1);
}
void main()
{
NODE* root;
Rebuild("abdcef","dbaecf",6,&root);
cout<<root->chValue<<endl;
}
页:
[1]