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

以下是代码

该函数的功能是根据一个字符串生成一个二叉树,
传入的字符串是该二叉树前序遍历的结果,
'#'代表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个回答

把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;
}
m0_37320910
追天荧火 我好像知道原因了,我free了只是把该空间释放了,指针没有变还是指向这一区域,但是因为被释放了所以可以再分配,接下来就把这个空间又分配了出去,所以才会出这种两个指针一样情况
大约一年之前 回复
m0_37320910
追天荧火 感谢你的回答,但是这样做没问题是没问题,但是前面分配的空间就浪费了,还有就是我挺想知道造成这样的原因是什么,还有就是这样的话叶节点下面不是空指针也不好遍历···
大约一年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问