[已解决]二叉搜索树人递归问题

cheyhu

请问二叉搜索树递归算法return返回的最终结果是什么？怎么找到所要找的关键字后一层一层地return回去，到最后回到了根

最佳答案

月排行榜 / 总排行榜

claws0n

2018-10-16 13:08:10

cheyhu 发表于 2018-10-16 01:41
一般行参上写 p  和 *p这样的表示的意思怎么区分？有时候还有**p  、&p?

没有 C 的基础？
BTNode BTree;
BTNode *p;
                   原型                                                  |                   调用
int fun(BTNode x);  // 接收结构体变量，返回整型     | fun(BTree);
int fun(BTNode *x); //接收结构体指针                     | fun(&BTree);  fun(p);
int fun(BTNode **x); //接收指向结构体指针的指针   | fun(&p);  <--------------v
int fun(BTNode *&x); //引用结构体指针的指针         | fun(p);    <--------  功能一样

跳转到最佳答案楼层

claws0n

看你是哪一种遍历方法。如果找到，返回关键字的值

cheyhu

claws0n 发表于 2018-10-15 10:29
看你是哪一种遍历方法。如果找到，返回关键字的值

就是这种查找方法，递归的最里层找到关键字后出来，一层一层到第一层，那返回的是啥？如果是直接跳出递归那就是返回关键字的所在层，但是这个不是啊

claws0n

cheyhu 发表于 2018-10-15 23:24
就是这种查找方法，递归的最里层找到关键字后出来，一层一层到第一层，那返回的是啥？如果是直接跳出递归 ...

嗯，层序遍历~ 应该很好理解
p 当前节点不为空，进入循环
进行 key 的比较
如果一样，返回当前节点
比较小，找左孩子
比较大，找右孩子
如果找不到，最后会跳出循环，返回空

这个不是递归，是循环/迭代~~

cheyhu

claws0n 发表于 2018-10-15 23:39
嗯，层序遍历~ 应该很好理解
p 当前节点不为空，进入循环
进行 key 的比较

抱歉抱歉，我传错了那个是插入的代码，这张才是查找的代码。。。。

claws0n

cheyhu 发表于 2018-10-16 00:15
抱歉抱歉，我传错了那个是插入的代码，这张才是查找的代码。。。。

这次是递归，但思路一样~
如果找到， return p;
找不到 return NULL;  //上面是 if(p == NULL) 已经到空了

cheyhu

claws0n 发表于 2018-10-16 00:22
这次是递归，但思路一样~
如果找到， return p;
找不到 return NULL;  //上面是 if(p == NULL) 已经到 ...

嗯  想通了，对了那个指针引用型是什么东西看不太懂
如  BTNODE *&p   //这是一个函数的形参

claws0n

cheyhu 发表于 2018-10-16 00:58
嗯  想通了，对了那个指针引用型是什么东西看不太懂
如  BTNODE *&p   //这是一个函数的形参

C 的话是要二级指针，调用时取地址
C++ 引用型就省去了取地址的动作，在函数的内部也不需要一直解引用

swap(int &x, int &y) ---> swap(a,b)

cheyhu

claws0n 发表于 2018-10-16 01:01
C 的话是要二级指针，调用时取地址
C++ 引用型就省去了取地址的动作，在函数的内部也不需要一直解引用
...

一般行参上写 p  和 *p这样的表示的意思怎么区分？有时候还有**p  、&p?

claws0n

cheyhu 发表于 2018-10-16 01:41
一般行参上写 p  和 *p这样的表示的意思怎么区分？有时候还有**p  、&p?

没有 C 的基础？
BTNode BTree;
BTNode *p;
                   原型                                                  |                   调用
int fun(BTNode x);  // 接收结构体变量，返回整型     | fun(BTree);
int fun(BTNode *x); //接收结构体指针                     | fun(&BTree);  fun(p);
int fun(BTNode **x); //接收指向结构体指针的指针   | fun(&p);  <--------------v
int fun(BTNode *&x); //引用结构体指针的指针         | fun(p);    <--------  功能一样