程序填空题：先序序列＋中序序列建立二叉树(递归法）
先序序列＋中序序列建立二叉树。
```c++
#include
#define N 100
using namespace std;
typedef struct BiNode
{
char data;
struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree CreateBTree(char a[],char b[],int n)
//由先序序列a[0..n-1]和中序序列b[0..n-1]建立二叉链存储结构bt
{ int k;
if (n<=0) return NULL;
char root=a[0]; //根结点值
BiTree bt=new BiNode;
bt->data=root;
for (k=0;k if (b[k]==root)
break;
bt->lchild=@@[CreateBTree(a+1,b,k)](2);
bt->rchild=@@[CreateBTree(a+k+1,b+k+1,n-k-1)](2);
return bt;
}
void LRD(BiTree T)
{
if(T){
LRD(T->lchild);
LRD(T->rchild);
cout << T->data;
}
}
int main()
{ BiTree T;
int n,i;
char a[N],b[N];
cin>>n;
for(i=0;i cin>>a[i];
for(i=0;i cin>>b[i];
T=CreateBTree(a,b,n);
LRD(T);
return 0;
}
```
### 输入样例：
第一行输入序列长度n，第二行输入n个字符表示二叉树先序遍历的序列，第三行输入n个字符表示二叉树中序遍历的序列
```in
9
ABDGHCEFI
GDHBAECIF
```
### 输出样例：
输出二叉树后序遍历的序列。
```out
GHDBEIFCA
```
答案：
第1空：CreateBTree(a+1,b,k)
第2空：CreateBTree(a+k+1,b+k+1,n-k-1)
```c++
#include
#define N 100
using namespace std;
typedef struct BiNode
{
char data;
struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree CreateBTree(char a[],char b[],int n)
//由先序序列a[0..n-1]和中序序列b[0..n-1]建立二叉链存储结构bt
{ int k;
if (n<=0) return NULL;
char root=a[0]; //根结点值
BiTree bt=new BiNode;
bt->data=root;
for (k=0;k
break;
bt->lchild=@@[CreateBTree(a+1,b,k)](2);
bt->rchild=@@[CreateBTree(a+k+1,b+k+1,n-k-1)](2);
return bt;
}
void LRD(BiTree T)
{
if(T){
LRD(T->lchild);
LRD(T->rchild);
cout << T->data;
}
}
int main()
{ BiTree T;
int n,i;
char a[N],b[N];
cin>>n;
for(i=0;i
for(i=0;i
T=CreateBTree(a,b,n);
LRD(T);
return 0;
}
```
### 输入样例：
第一行输入序列长度n，第二行输入n个字符表示二叉树先序遍历的序列，第三行输入n个字符表示二叉树中序遍历的序列
```in
9
ABDGHCEFI
GDHBAECIF
```
### 输出样例：
输出二叉树后序遍历的序列。
```out
GHDBEIFCA
```
答案：
第1空：CreateBTree(a+1,b,k)
第2空：CreateBTree(a+k+1,b+k+1,n-k-1)
