[速记]关于指针，引用和递归和解递归——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=key;
node->leftNode=nullptr;
node->rightNode=nullptr;
root=node;
return root;
}
else if (root->data==key)
{
return root;
}
else if (root->data<key)
{
return (Insert_Tree(root->rightNode,key));
}
else if (root->data>key)
{
return(Insert_Tree(root->leftNode,key));
}}

然后，我自己实现了一下解递归的实现

//这个方法是错误的
TreeNode* Insert_Tree2(TreeRoot &root,TypeData key)
{
TreeNode *p=root;
while (p)
{
if (p->data==key)
{
return p;
break;
}
else if (p->data>key)
{
p=p->leftNode;
}
else
{
p=p->rightNode;
}
}
if (!p)
{
p=new TreeNode;
p->data=key;
p->leftNode=nullptr;
p->rightNode=nullptr;
return p;
}}

看似，没有什么问题，实际上却犯了一个灰常严重的错误

我们可以看到，两种方式都是以引用的形式传入了根节点，为什么用引用？

因为我们插入的时候肯定会造一个新结点，然后要把它接到原来的树体系当中，第一种递归的方式中，最后造结点的时候

TreeNode *node=new TreeNode;
node->data=key;
node->leftNode=nullptr;
node->rightNode=nullptr;
root=node;
return root;可以看到，标黑的位置，这个时候root是以引用的方式传入的，这个事实上直接更改了原来树体系中的结点而在，解递归的实现当中，虽然是以引用的方式传入的参数，但是我们用了一个指针局部变量来代替他，最后的时候

p=new TreeNode;
p->data=key;
p->leftNode=nullptr;
p->rightNode=nullptr;
return p;
他是这样执行的，这里的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='q';
q->left=q;
q->right=q;
std::cout<<l->data;
std::cout<<q->data;

最后，总结一下：

1.要注意！修改指针和修改指针共同指向的内容是两回事！

2.凡是用到链式存储，当要改变结点之间的关系，或者增加结点的时候，这个时候最好用对指针的引用（二级指针也行，不过不推荐）。

3.当第二种情况用到递归的时候，解递归一定要谨慎，最好不要解递归！

4.事实上，只要不更改涉及到更改指针本身，一般都不会出现这种问题！此时实际上就是涉及到了更改了指针本身，却没有对原来的内容更新