引子–二叉树交换左右子树

昨日的题目大概是这样？

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void change(bitnode *&t, int x, int y)
{
	bitnode *temp = new bitnode;
	if (t)
	{
		if (t==NULL)return//若是根节点为NULL，递归结束
		temp = t->lchild;
		t->lchild = t->rchild;
		t->rchild = temp;
		change(t->lchild, x, y);
		change(t->rchild, x, y);
	}
}

（代码是我网上dang来的，我懒得传图片了）只不过在第一行的位置应该是忘记写了*，据我回忆的几个细节大概是这样的

不完全代码：

1
2
3
4
5
6
7
8

void switchLRTree(bitree &T)
{
    bitnode *temp = T->lchild;
    T->lchild = T->rchild;
    T->rchild = temp;
    switchLRTree .....
        .....
}

问题主要出在两处，一个是函数传入的是树的地址而非指针，以至于在函数运行过程中修改成了树的值在函数中所被指向的指针的值。感觉不太好理解，没关系，我们先再来复习一下关于在初学函数时所使用的形参和实参的概念。

形参和实参

对于一个函数，内部所使用的变量被成为局部变量，函数外所定义的变量则是全局变量，相对于全局变量而言，局部变量仅能在函数内部使用。而在函数的调用过程中，函数所定义并使用的变量是形参，在使用函数调入数据时，会将实参的值赋予形参后，在函数内部进行运算，但是却只会修改函数内部的形参，无法对实参产生影响。

也就是如果我们想要用函数修改函数之外的变量的值，就必须要使用指针，传入变量的地址而非值，通过地址准确修改其所指向的值。（在二叉树这里的swap如果按照惯性思维很容易想岔，因为调用的是指针的指针，也就是在第三层）

指针和地址

那么怎么才能升到大气层呢？我们还是得仔细考虑一下指针和地址的关系（*和&）

变量都放置在内存中，内存的每个字节都有一个成为地址的编号，而变量的地址则是这一定数目的字节的第一个的地址。

使用int* a则会定义一个指向int型变量的指针

变量名前面加&则是去该变量的地址

倘若在这之后使用a = &b，则是将变量b的地址存放到a之中，这时，*a便是a所指向的变量。（这里仅仅是指向的变量，而非变量的值，大概就是人名和人身的区别吧）

因此回到引子，如果我们想要交换两个普通的变量的值，则需要在swap函数中如此定义

1

void swap(int* a, int* b);

% cq %

当然这里需要注意的是，指针虽然也是一种变量，但是却不推荐拿来直接用(比如定义一个整形指针i，然后给*i赋值当整形变量用)，因为你给指针赋值前他是不确定的，搞不好他所代表的内存单元偏偏就不能写入呢？

% endcq %

结构体以及之后的二叉树

当swap和二叉树交错在一起，事情就变得更加棘手了，不过我们首先来看看结构体里的指针是怎么搞的。

this 指向当前变量的指针

this->x 当前对象的成员变量x （等价于(*this).x）

这个时候再回去看文章开头的代码，发现好像有些许不太优雅的地方，修改如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

void change(bitnode *t, int x, int y)
{
	bitnode *temp = new bitnode;
	if (t)
	{
		temp = t->lchild;
		t->lchild = t->rchild;
		t->rchild = temp;
		change(t->lchild, x, y);
		change(t->rchild, x, y);
	}
}

在二叉树定义中，节点的类型是bitnode的话，左右子节点的类型就是bitnode *，也就是指向节点类型的指针。所以指针对指针，值对值，不能搞混。

（好™复杂）

所以错在两处，函数应当调入指针，然后用结构体构造好temp后再用来倒腾。