首頁猿問下面有我的建樹函數(shù)，有注釋的，請大...

下面有我的建樹函數(shù)，有注釋的，請大佬幫忙看看

C

蕭十郎 2023-03-06 20:16:15

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); //開辟數(shù)組strncpy(L,level+1,len-1); //舍棄第一個L[len-1]=0;T->lchild=NULL;T->rchild=NULL;BuildTree(L,inorder,T); //調(diào)用建樹函數(shù)return ;}else{pos=p-inorder; //得到中序遍歷左子樹字符串長度T->data=level[0]; //為根節(jié)點賦值T->lchild=NULL;T->rchild=NULL;}if(pos!=0) //左子樹的遞歸調(diào)用{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) //右子樹的遞歸調(diào)用{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);}}運行結(jié)果：2輸入：CBABCA輸出：CB燗燘AC輸入：BACDEDAEBC輸出：BAD燛C燚EA谻B

查看完整描述

1 回答

慕妹3242003

TA貢獻1824條經(jīng)驗獲得超6個贊

#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;//要函數(shù)體內(nèi)新建
for(int i=1;i<lev.size();i++){
if(vis[lev[i]]==true)
tempLeft.push_back(lev[i]);
else
tempRight.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;
}