Question

C语言根据层次遍历和中序遍历求二叉树的前序遍历和后序遍历。下面有我的建树函数，有注释的。

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]);
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;
}

Answer 2

这段代码不完整，缺少太多，另外不知你要问什么。

追问

根据提供的层次遍历和中序遍历还原二叉树。

如
输入：
CBA
BCA
输出：（先序遍历和后序遍历）
CBA
BAC

以上是我根据中序遍历和层次遍历还原二叉树的代码；
我的错误输出也贴上去了。这样能明白吗？
其它代码与这段代码没有关联，只需要调用这个函数即可

追答

你这段代码的思想是什么呢？