由中序遍历和层次遍历还原二叉树。C语言实现

题目链接：http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=10609
如果有兴趣帮我的代码找错当然感激不尽，没兴趣就贴出自己的想法和代码。
由于字数限制，只贴出我的还原函数。
void BuildTree(char *level,char *inorder,pBiTree T)
{
int i;
int len=strlen(level); //取得层次遍历长度
int pos=0;
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;
BuildTree(L,inorder,T); //调用建树函数
return ;
}
pos=p-inorder; //得到中序遍历左子树字符串长度
T->data=level[0]; //为根节点赋值
T->lchild=NULL;
T->rchild=NULL;
if(pos!=0) //左子树的递归调用
{
T->lchild=(pBiTree)malloc(sizeof(BiNode));
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,T->lchild);
}
if(*(p+1)>='A'&&*(p+1)<='Z') //右子树的递归调用
{
T->rchild=(pBiTree)malloc(sizeof(BiNode));
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,T->rchild);
}
}

#include
#include
#include
#include
#include


typedef int data_t;
typedef struct node
{
    data_t data;
    struct node *lchild, *rchild;
}btree;


btree *create_btree(void);
void preorder_btree(btree *bt);
void inorder_btree(btree *bt);
void postorder_btree(btree *bt);
int depth_btree(btree *bt);
void free_btree(btree **bt);
void exchange_btree(btree *bt);
void print_btree(btree *bt); //先序遍历的非递归算法


int main(int argc, const char *argv[])
{
    btree *bt = create_btree(); 
    preorder_btree(bt);
    printf("\n");
    printf("depth=%d\n", depth_btree(bt));
    exchange_btree(bt);
    preorder_btree(bt);
    printf("\n");
    print_btree(bt);
    printf("\n");
    free_btree(&bt);
    preorder_btree(bt);
    printf("\n");


    return 0;
}


btree *create_btree(void)
{
    int n;
    scanf("%d", &n);
    if (n == 0) 
    {
        return NULL;
    }
    btree *bt = (btree*)malloc(sizeof(btree));
    bt->data = n;
    bt->lchild = create_btree();
    bt->rchild = create_btree();


    return bt;
}


void preorder_btree(btree *bt)
{
    if (bt) 
    {
        printf("%d,", bt->data);
        preorder_btree(bt->lchild);
        preorder_btree(bt->rchild);
    }
}


void inorder_btree(btree *bt)
{
    if (bt) 
    {
        inorder_btree(bt->lchild);
        printf("%d,", bt->data);
        inorder_btree(bt->rchild);
    }
}


void postorder_btree(btree *bt)
{
    if (bt) 
    {
        postorder_btree(bt->lchild);
        postorder_btree(bt->rchild);
        printf("%d,", bt->data);
    }
}


int depth_btree(btree *bt)
{
    if (!bt) 
    {
        return 0;
    }
    int ldepth = depth_btree(bt->lchild);
    int rdepth = depth_btree(bt->rchild);


    return ldepth > rdepth ? ldepth+1 : rdepth+1;
}


void free_btree(btree **bt)
{
    if (*bt) 
    {
        free_btree(&(*bt)->lchild);
        free_btree(&(*bt)->rchild);
        free(*bt);
        *bt = NULL;
    }
}


void exchange_btree(btree *bt)
{
    if (bt) 
    {
        exchange_btree(bt->lchild);
        exchange_btree(bt->rchild);


        btree *tmp = bt->lchild;
        bt->lchild = bt->rchild;
        bt->rchild = tmp;
    }
}


void print_btree(btree *bt) //先序遍历的非递归算法
{
    //创建一个栈
    btree *stack[20];
    int top = 0;


    if (bt) //根不空，根入栈
    {
        stack[top] = bt;
        top++;
    }
    while(top) //当栈不空
    {
        top--;
        btree *tmp = stack[top];//出栈，访问
        printf("%d,", tmp->data);


        if (tmp->rchild) //右子树不空，右子树入栈
        {
            stack[top] = tmp->rchild;
            top++;
        }
        if (tmp->lchild) //左子树不空，左子树入栈
        {
            stack[top] = tmp->lchild;
            top++;
        }
    }
}
//

对于层次遍历的实现是用队列，根节点入队列然后根节点出队列的同时左节点右节点入队列，这样依次，出一次队列对应出队列的节点左右节点如队列，没有就不入。

经测，该代码已经修改正确，只需在void buildtree(char *level,char *inorder,pbitree t)这里的最后一个变量t改为引用即可。还有一个地方判断调用右子树的地方的判断条件。 #include  #include  #include  typedef struct _bitree {     char data;     struct _bitree *lchild;     struct _bitree *rchild; }binode, *pbitree; void buildtree(char *level,char *inorder,pbitree &t) {     int i;     int len=strlen(level);  //取得层次遍历长度     int pos=0;     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;         buildtree(l,inorder,t);     //调用建树函数         return ;     }     pos=p-inorder;      //得到中序遍历左子树字符串长度     t->data=level[0];   //为根节点赋值     t->lchild=null;     t->rchild=null;     if(pos!=0)  //左子树的递归调用     {         t->lchild=(pbitree)malloc(sizeof(binode));         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,t->lchild);     }     if(pos < strlen(inorder)-1)      //右子树的递归调用     {         t->rchild=(pbitree)malloc(sizeof(binode));         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,t->rchild);     } } void priorder(pbitree t) {     if (t != null){         printf ("%c", t->data);         priorder(t->lchild);         priorder(t->rchild);     } } void postorder(pbitree t) {     if (t != null){         postorder(t->lchild);         postorder(t->rchild);         printf ("%c", t->data);     } } void freenode(pbitree &t) {     if (t != null){         freenode(t->lchild);         freenode(t->rchild);         free(t);     } } int main() {     pbitree root;     char level[28], inorder[28];     int n;     scanf ("%d", &n);     //fflush(stdin);     getchar();     while (n --){         scanf ("%s%s", level, inorder);         root = (pbitree)malloc(sizeof(binode));         buildtree(level, inorder, root);         priorder(root);         printf ("\n");         postorder(root);         printf ("\n");         //freenode(root);     }     return 0; }