前段代码已经定义了常见的二叉树结构体，搞不清参数部分最后一个*&father为什么是这样？直接*father不行吗？

Question

BSTNode * Search(BSTree root,DataType x,BSTNode *&father)
_{ 
BSTNode*p=root;father =NULL;
while(p!=NULL&&p->data!=x){
                                    father=p;
                                                                        if(x<p->data) p=p->lchild;
                                                                        else p=p->rchild;
                                                                        }
                                                                        return p;
};

Answer 1

BSTNode *&father
的含义是定义了一个对BSTNode *指针的引用类型的参数
之所以要引用，是因为你的函数内有
father =NULL;
father=p;
这样的代码，让father指向改变。
如果没有引用（&），在函数内改变father指针的指向，不会作用到调用这个函数的主程序上。

看下面一个简单的例子：

#include <iostream>
using namespace std;

void set(int *& a)
{
    a = new int;
    *a=2;
}

int main()
{
    int i = 1;
    int *a = &i;
    set(a);
    cout << *a << endl;
    cout << i;
    return 0;
}

结果
2
1

这个程序中set分配了一个新的内存空间，并且改变a的指向。
主程序输出 cout << *a的时候，输出的就是这个新分配内存上的2
下面输出i的那一行可以看出，i还是1。
如果去掉&
则程序输出1，因为调用set后，虽然函数内的a指向了新的内存，但是主程序的a并不受影响，还是指向局部变量i的地址。

#include <iostream>
using namespace std;

void set(int * a)
{
    a = new int;
    *a=2;
}

int main()
{
    int i = 1;
    int *a = &i;
    set(a);
    cout << *a << endl;
    *a=3;
    cout << i;
    return 0;
}

这个程序因此输出
1
3
因为set之后a还是指向i的地址，所以通过它改变，i也就改变了。