m0_37320910
追天荧火
采纳率100%
2019-01-04 21:56 阅读 429

一个非递归树的生成算法问题

10

以下是代码

该函数的功能是根据一个字符串生成一个二叉树,
传入的字符串是该二叉树前序遍历的结果,
'#'代表NULL,
例如:"abd#e##fg###c##".

bintree createbintree(char *s) {
    bintree stack[Maxsize];
    int top = 0;
    bintree t = (bintree)malloc(sizeof(bintnode));
    bintree p = t;
    while ((*s)!='\0')
    {
        if ((*s)!='#')
        {
            p->data = *s;
            stack[top++] = p;
            p->lchild = (bintree)malloc(sizeof(bintnode));
            p = p->lchild;
        }
        else
        {
            if(p!=NULL)
                free(p);
            if (top == 0)return t;
            p = stack[--top];
            p->rchild = (bintree)malloc(sizeof(bintnode));
            p = p->rchild;
        }
        s++;
    }
    return t;
}

图片说明
在第一次遇到#的时候,就是运行到上图所示代码的地方,
在执行完p=stack[--top]后,p的内容是这样的

图片说明

可是在执行p->rchild = (bintree)malloc(sizeof(bintnode));后

图片说明
左右孩子的地址空间一样了,这是什么造成的?

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

1条回答 默认 最新

  • 已采纳
    caozhy 从今以后生命中的每一秒都属于我爱的人 2019-01-05 00:16

    把free(p)去掉看看

    #include "stdlib.h"
    
    #define Maxsize 100
    
    typedef struct bintnode
    {
        char data;
        bintnode * lchild;
        bintnode * rchild;
    } *bintree;
    
    bintree createbintree(char *s) {
        bintree stack[Maxsize];
        int top = 0;
        bintree t = (bintree)malloc(sizeof(bintnode));
        bintree p = t;
        while ((*s) != '\0')
        {
            if ((*s) != '#')
            {
                p->data = *s;
                stack[top++] = p;
                p->lchild = (bintree)malloc(sizeof(bintnode));
                p = p->lchild;
            }
            else
            {
                if (p != NULL)
                {
                    //free(p);
                }
                if (top == 0)return t;
                p = stack[--top];
                p->rchild = (bintree)malloc(sizeof(bintnode));
                p = p->rchild;
            }
            s++;
        }
        return t;
    }
    
    int main()
    {
        char * s = "abd#e##fg###c##";
        bintree tree = createbintree(s);
        return 0;
    }
    
    点赞 评论 复制链接分享

相关推荐