通过传递指针代替函数返回值

ing

通过不断的递归，最后参数 BiTree *r 只剩一个结点



为什么最后指针的值(指针 r 并不只有一个结点)并没有被修改？我通过不断的递归修改的指针值没有被保留


这将导致依次插入3,4,2,5,9输出的是2 3 9；因为 r 指针位置没有成功移动到 data:4 的结点位置。

#include<malloc.h>
#include<stdio.h>
#include <stdbool.h>

#define KeyType int
#define ElemType int

typedef struct BiTNode
{
    ElemType data;
    struct BiTNode *l_child, *r_child;
}BiTNode,*BiTree;

//r 是 p 结点的父结点
bool searchBST(BiTree p,KeyType key,BiTree *r)
{
    if (!p)
    {
//在该方法结束后，回到 insertBST 时 p、r 的值并没有像预期那样，与这的 p、r 相同
        p = *r;
        return false;
    }
    else if (key == p->data)
    {
        return true;
    }
    else if (key < p->data)
    {
        searchBST(p->l_child,key,&p);
    }
    else
    {
        searchBST(p->r_child,key,&p);
    }
}

bool insertBST(BiTree *t,ElemType e)
{
//指针指向了 t，因此 r 增加结点 t 也会增加
    BiTree *r = t;
    BiTree p = *r;
//搜索方法调用后，指针p、r 均未改变？？
    if (!searchBST(p,e,r))
    {
        BiTNode *s = (BiTNode*)malloc(sizeof(BiTNode));
        s->data = e;
        s->r_child = s->l_child = NULL;

        if (!(*t))
            *r = s;
        else if ((*t)->data > e)
        {
            (*r)->l_child = s;
        }
        else
            (*r)->r_child = s;
        return true;
    }
    return false;
}

bool delete(BiTree *t)
{
    BiTree q,s;
    if (!(*t)->l_child && !(*t)->r_child)
        (*t) = NULL;
    else if (!(*t)->l_child)
    {
        q = *t;
        *t = (*t)->r_child;
        free(q);
    }
    else if (!(*t)->r_child)
    {
        q = *t;
        *t = (*t)->l_child;
        free(q);
    }
    else
    {
        q = *t;
        s = (*t)->l_child;
        while (!(*t)->r_child)
        {
            q = s;
            s = s->r_child;
        }
        (*t)->data = s->data;
        //判断结点 p 的左子树 s 是否有右子树，分为两种情况讨论
        if(q != *t)
        {
            q->r_child = s->l_child;//若有，则在删除直接前驱结点的同时，令前驱的左孩子结点改为 q 指向结点的孩子结点
        }
        else
        {
            q->l_child = s->l_child;//否则，直接将左子树上移即可
        }

        free(s);
    }
    return true;
}

bool deleteBST(BiTree *t,ElemType e)
{
    if (e == (*t)->data)
    {
        delete(t);
        return true;
    }
    else if (e < (*t)->data)
        deleteBST(&(*t)->l_child,e);
    else if (e > (*t)->data)
        deleteBST(&(*t)->r_child,e);
    return false;
}

//中序输出
void order(BiTree t)
{
    if (!t)
        return;
    order(t->l_child);
    printf("%d ",t->data);
    order(t->r_child);
}

int main(int argc, char* argv[])
{
    BiTree t = NULL;
    int a[5] = {3,4,2,5,9};
    for (int i = 0; i < 5; ++i) {
        insertBST(&t,a[i]);
    }
    printf("中序遍历二叉排序树：\n");
    order(t);
    printf("\n删除3后，中序遍历二叉排序树：\n");
    deleteBST(&t,3);
    order(t);

    return 0;
}

huayugongju

问题出在这个地方：bool searchBST(BiTree p,KeyType key,BiTree *r)  
第一个入参 p 是临时变量，没有办法做出参（将修改后的值带出），这里推荐使用二重指针才解决修改指针地址。

修改为：bool searchBST(BiTree **p,KeyType key,BiTree *r)  
调用：searchBST(&p->l_child,key,&p);
赋值：*p = r

huayugongju

huayugongju 发表于 2020-2-5 23:44
问题出在这个地方：bool searchBST(BiTree p,KeyType key,BiTree *r)  
第一个入参 p 是临时变量，没有办 ...

你调试看看，这个就是问题的本质“”通过二级指针才能修改指针的值，做出参“”