首页 > 代码库 > [速记]关于指针,引用和递归和解递归——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++