基于完全前序序列建立二叉树

Question

这是一个困扰了我许久的问题, 虽然网上有很多完全前序序列建立二叉树的例子, 但我很想把我自己的代码改对, 而不是绕过去看正确答案.

typedef int ElemType;
结构体定义:

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

我写的错误的函数:

void CreateBTbyPreOrder(BiTree BT){
    int a;
    scanf("%d",&a);
    if(a==-1) {
        BT=NULL;
    }
    else{
        BT = (BiTNode*)malloc(sizeof(BiTNode));
        BT->data = a;
        CreateBTbyPreOrder(BT->lchild);
        CreateBTbyPreOrder(BT->rchild);
    }
    return;
}

main调用错误函数方法:

int main(){
    BiTree BT2;
    CreateBTbyPreOrder(BT2);  
    PreOrder(BT2);printf("\n");
    return 0;
}

输入:
1 4 2 -1 -1 5 -1 -1 3 -1 6 -1 -1
现象:
运行时错误, 程序崩掉, 无法继续运行.

网上找到了一个可以正确运行的写法:

BiTree CreateBT(){
    int a;
    BiTree BT;
    scanf("%d", &a);
    if(a==-1) {
        BT=NULL;
    }
    else{
        BT=(BiTree)malloc(sizeof(BiTNode));
        BT->data = a;
        BT->lchild = CreateBT();
        BT->rchild = CreateBT();
    }
    return BT;
}

调用方法:

int main(){
    BiTree BT3 = CreateBT();
    PreOrder(BT3);printf("\n");
}

输入:
1 4 2 -1 -1 5 -1 -1 3 -1 6 -1 -1
现象:
142536

我和网上的写法有什么区别吗? 我认为无非是一个传一个指针进去, 一个是返回来一个指针. 为什么我的就是不对呢?

完整代码:https://paste.ubuntu.com/p/9rtfv7svX4/

Answer 1

main函数里BT2是一个在地址A的指针, 指向一个空间B(没有malloc, 只是一个随机地址), 当它被传进函数时, 实际上并不是操作的一个个体, 但是是操作的一个内容, 换句话说: 函数里的BT是一个在地址C的指针, 只不过指向的空间还是B(上面的随机地址). 在函数内执行malloc以后, 这个在地址C的指针指向了一个新的地址空间D, 而函数没有返回, 函数结束以后, 地址C的指针被销毁了, D空间也没有free, 成为了一个无法访问的地址空间, 同时BT2无法得知真正的操作后应该指向的空间在哪里, 也就是说, 你在函数里创建的根节点在地址D, 而因为没有返回, main函数里创建的BT2依旧指向着B(那个随机地址). 所以错了.
同样的道理, 这是一个递归函数, 那么每次创建左孩右孩都没有被返回. 也就是说白白创建了结点, 却不返回指针, 不知道创建在了哪里.... 每一个结点之间都没有被连接上.

Answer 2

区别是CreateBTbyPreOrder的错误是没有把分配的指针(BT)返回给调用者，CreateBT会把BT通过返回值返回给调用者。

你如果要传递指针，应该把指针的指针传过去：

void CreateBTbyPreOrder(BiTree * BT){
    int a;
    scanf("%d",&a);
    if(a==-1) {
        *BT=NULL;
    }
    else{
        *BT = (BiTNode*)malloc(sizeof(BiTNode));
        *BT->data = a;
        CreateBTbyPreOrder(*BT->lchild);
        CreateBTbyPreOrder(*BT->rchild);
    }
    return;
}

int main(){
    BiTree BT2;
    CreateBTbyPreOrder(&BT2);  
    PreOrder(BT2);printf("\n");
    return 0;
}