首页 > 代码库 > [速记]关于指针,引用和递归和解递归——C++
[速记]关于指针,引用和递归和解递归——C++
在写基于二叉排序树的查找时,分为三个过程
1.二叉排序树的插入
2.二叉排序树的建立
3.基于二叉排序树的查找
其中第三部可以递归方式实现,也可以用while循环解递归,于是我想也解解第一步的递归,看看行不行,结果给了我当头一棒,解递归失败!
最后我分析了一下原因:
首先看一下,原来递归的实现方式
typedef struct _TreeNode { struct _TreeNode *leftNode; struct _TreeNode *rightNode; TypeData data; }TreeNode,*TreeRoot; //返回插入位置的结点 TreeNode* Insert_Tree(TreeRoot &root,TypeData key) { if (!root) { TreeNode *node=new TreeNode; node->data=http://www.mamicode.com/key;>
然后,我自己实现了一下解递归的实现
//这个方法是错误的 TreeNode* Insert_Tree2(TreeRoot &root,TypeData key) { TreeNode *p=root; while (p) { if (p->data=http://www.mamicode.com/=key)>
看似,没有什么问题,实际上却犯了一个灰常严重的错误
我们可以看到,两种方式都是以引用的形式传入了根节点,为什么用引用?
因为我们插入的时候肯定会造一个新结点,然后要把它接到原来的树体系当中,第一种递归的方式中,最后造结点的时候
TreeNode *node=new TreeNode; node->data=http://www.mamicode.com/key;>root=node; return root;
可以看到,标黑的位置,这个时候root是以引用的方式传入的,这个事实上直接更改了原来树体系中的结点
而在,解递归的实现当中,虽然是以引用的方式传入的参数,但是我们用了一个指针局部变量来代替他,最后的时候
p=new TreeNode; p->data=http://www.mamicode.com/key;>他是这样执行的,这里的p怎样得到的呢?
p=上一个p的left,
这样一种方式的后果是什么呢?
它改变了两个指针共同指向的内容,却无法改变另一个指针本身,是不是觉得无法理解?
不要紧,p是根据上一个父节点的left来赋值的,假设上一个父节点叫做f
那么,也就是
p=f->left;
这个时候p和f->left都为nullptr,
一直到这个时候,都没有问题
然后我们一个劲儿地去更改p的内容,
这个时候,没错,我们通过p更改了两者共同指向的内容,可是!
f->left一直都是nullptr
你改的再多,依然与我无关啊!
不理解的,再看一个程序
Node *p=new Node; p->left=nullptr; p->right=nullptr; Node *l=p->left; Node *q=p->left; q=new Node; q->data=http://www.mamicode.com/‘q‘;>
最后,总结一下:
1.要注意!修改指针和修改指针共同指向的内容是两回事!
2.凡是用到链式存储,当要改变结点之间的关系,或者增加结点的时候,这个时候最好用对指针的引用(二级指针也行,不过不推荐)。
3.当第二种情况用到递归的时候,解递归一定要谨慎,最好不要解递归!
[速记]关于指针,引用和递归和解递归——C++
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。