算法如下: 1)先在后序序列中找到根结点, 2)在中序序列中找到根结点位置,(可以将二叉树分为左子树和右子树) 3)用同样的办法构造左子树 。 4)用同样的办法构造右子树。
算法如下:
BinaryTree* Creat_Node(char ch)
{
BinaryTree* root;
root = new BinaryTree;
root->data = ch;
root->lchild = root->rchild = NULL;
return root;
}
BinaryTree* Mid_Post_Create_Pre(char* mid,char*post,int N)
{
if(!mid||!post||N<0){
cout<<"输入出错!"<<endl;
return NULL;
}
int root_index = 0;
for(root_index = 0 ; root_index < N ; root_index++){
if(mid[root_index] == post[N-1]){
break;
}
}
if(root_index == N){
cout<<"中序序列与后序序列不匹配!"<<endl;
return NULL;
}
BinaryTree* root = this->Creat_Node(post[N-1]);
if(root_index > 0){
root->lchild = root->Mid_Post_Create_Pre(mid,post,root_index);
}
if(N-root_index-1 > 0){
root->rchild = root->Mid_Post_Create_Pre(mid+root_index+1,post+root_index,N-root_index-1);
}
return root;
}