下面有我的建树函数，有注释的，请大佬帮忙看看

Question

void BuildTree(char *level,char *inorder,pBiTree T)
{
int i;
int len=strlen(level); //取得层次遍历长度
int pos;
if(len==0)
return ;
char *p=strchr(inorder,level[0]);
if(p==NULL) //如果为空则抛弃第一个，跳到下一个；
{
char *L=(char*)malloc(sizeof(char)*len); //开辟数组
strncpy(L,level+1,len-1); //舍弃第一个
L[len-1]=0;
T->lchild=NULL;
T->rchild=NULL;
BuildTree(L,inorder,T); //调用建树函数
return ;
}else{
pos=p-inorder; //得到中序遍历左子树字符串长度
T->data=level[0]; //为根节点赋值
T->lchild=NULL;
T->rchild=NULL;
}
if(pos!=0) //左子树的递归调用
{
pBiTree left;
T->lchild=(pBiTree)malloc(sizeof(BiNode));
left=T->lchild;
char *left_level=(char*)malloc(sizeof(char)*len);
char *left_inor=(char*)malloc(sizeof(char)*(pos));
strncpy(left_level,level+1,len-1); //舍去层次遍历第一个
strncpy(left_inor,inorder,pos); //截取左子树字符串
left_level[len-1]=0;
left_inor[pos]=0;
BuildTree(left_level,left_inor,left);
}
if(pos!=len-1) //右子树的递归调用
{
pBiTree right;
T->rchild=(pBiTree)malloc(sizeof(BiNode));
right=T->rchild;
char *right_level=(char*)malloc(sizeof(char)*(len));
char *right_inor=(char*)malloc(sizeof(char)*(len-pos));
strncpy(right_level,level+1,len-1);
strncpy(right_inor,inorder+pos+1,len-pos-1);
right_level[len-1]=0;
right_inor[len-pos-1]=0;
BuildTree(right_level,right_inor,right);
}
}
运行结果：

2
输入：
CBA
BCA
输出：
CB燗
燘AC

输入：
BACDE
DAEBC
输出：
BAD燛C
燚EA谻B

Answer 1

#include"cstdio"#include"vector"#include"cstring"#include"algorithm"using namespace std;const int maxn =30;struct node{int data;node* lchild;node* rchild;};int n;int in[maxn];bool vis[maxn]={false};vector<int> lev;node* create(vector<int> lev,int inl,int inr){if(lev.size()==0) return NULL;if(inl>inr) return NULL;//printf("00\n");node* root= new node;root->data =lev[0];int k;for(k=inl;k<=inr;k++){if(lev[0]==in[k])break;}for(int j=inl;j<=k-1;j++)vis[in[j]]=true;vector<int> tempLeft,tempRight;//要函数体内新建for(int i=1;i<lev.size();i++){if(vis[lev[i]]==true)tempLeft.push_back(lev[i]);elsetempRight.push_back(lev[i]);}root->lchild =create(tempLeft,inl,k-1);root->rchild =create(tempRight,k+1,inr);return root;}void preorder(node* root){if(root==NULL)return;printf("%d ",root->data);preorder(root->lchild);preorder(root->rchild);}int main(){scanf("%d",&n);int x;for(int i=0;i<n;i++){scanf("%d",&x);lev.push_back(x);}for(int j=0;j<n;j++)scanf("%d",&in[j]);node *root =create(lev,0,n-1);preorder(root);return 0;}