程序填空题：后序＋中序序列构造二叉树（递归法）
后序＋中序序列构造二叉树（递归法）。
```c++
#include
#include
#include
#define N 1000
using namespace std;
struct node{
char data;
struct node * lchild;
struct node * rchild;
};
struct node * createtree(char *post,char *in,int len)
{ if(len == 0) return NULL;
int i=0;
int m=@@[post[len-1]](2);
struct node *root;
while(i root=(struct node *)malloc(sizeof(struct node));
root->data=m;
root->lchild=@@[createtree(post,in,i)](2);
root->rchild=@@[createtree(post+i,in+i+1,len-i-1)](2);
return root;
}
void Preorder(struct node * root)
{
if(root)
{
cout<data;
Preorder(root->lchild);
Preorder(root->rchild);
}
}
int main()
{
int n,i;
char post[N];
char in[N];
cin>>n;
for(i=0;i cin>>post[i];
for(i=0;i cin>>in[i];
struct node *root=createtree(post,in,n);
Preorder(root);
return 0;
}
```
### 输入样例：
第一行输入序列长度n，第二行输入n个字符表示二叉树后序遍历的序列，第三行输入n个字符表示二叉树中序遍历的序列
```in
9
GHDBEIFCA
GDHBAECIF
```
### 输出样例：
输出二叉树先序遍历的序列。
```out
ABDGHCEFI
```
答案：
第1空：post[len-1]
第2空：createtree(post,in,i)
第3空：createtree(post+i,in+i+1,len-i-1)
```c++
#include
#include
#include
#define N 1000
using namespace std;
struct node{
char data;
struct node * lchild;
struct node * rchild;
};
struct node * createtree(char *post,char *in,int len)
{ if(len == 0) return NULL;
int i=0;
int m=@@[post[len-1]](2);
struct node *root;
while(i
root->data=m;
root->lchild=@@[createtree(post,in,i)](2);
root->rchild=@@[createtree(post+i,in+i+1,len-i-1)](2);
return root;
}
void Preorder(struct node * root)
{
if(root)
{
cout<
Preorder(root->lchild);
Preorder(root->rchild);
}
}
int main()
{
int n,i;
char post[N];
char in[N];
cin>>n;
for(i=0;i
for(i=0;i
struct node *root=createtree(post,in,n);
Preorder(root);
return 0;
}
```
### 输入样例：
第一行输入序列长度n，第二行输入n个字符表示二叉树后序遍历的序列，第三行输入n个字符表示二叉树中序遍历的序列
```in
9
GHDBEIFCA
GDHBAECIF
```
### 输出样例：
输出二叉树先序遍历的序列。
```out
ABDGHCEFI
```
答案：
第1空：post[len-1]
第2空：createtree(post,in,i)
第3空：createtree(post+i,in+i+1,len-i-1)
