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

论坛 期权论坛 期权     
傻十三1314   2018-4-26 13:45   7011   1
题目链接:http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=10609
如果有兴趣帮我的代码找错当然感激不尽,没兴趣就贴出自己的想法和代码。
由于字数限制,只贴出我的还原函数。
void BuildTree(char *level,char *inorder,pBiTree T)
{
...题目链接: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)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);
    }
}展开
分享到 :
0 人收藏

1 个回复

倒序浏览
wchyumo2011  1级新秀 | 2018-4-30 02:07:34 发帖IP地址来自
经测,该代码已经修改正确,只需在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聽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;
}

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

积分:
帖子:
精华:
期权论坛 期权论坛
发布
内容

下载期权论坛手机APP