通过传递指针代替函数返回值
本帖最后由 ing 于 2020-2-6 12:09 编辑通过不断的递归，最后参数 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 = {3,4,2,5,9};
for (int i = 0; i < 5; ++i) {
insertBST(&t,a);
}
printf("中序遍历二叉排序树：\n");
order(t);
printf("\n删除3后，中序遍历二叉排序树：\n");
deleteBST(&t,3);
order(t);
return 0;
}
``` 问题出在这个地方：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 发表于 2020-2-5 23:44
问题出在这个地方：bool searchBST(BiTree p,KeyType key,BiTree *r)
第一个入参 p 是临时变量，没有办 ...
你调试看看，这个就是问题的本质“”通过二级指针才能修改指针的值，做出参“”
页:
[1]