二叉树创建为什么用二级指针

最近看二叉树的插入（创建）用的是二级指针，一开始有点困惑，再难的东西它也有个最简单的原因。

一、理解二级指针

例子1 首先看一个简单的 

#include <iostream>
using namespace std;
int change(int b)
{
    b=10;
    return b;
}
int main()
{
    int a=5;
    change(a);
    cout<<a<<endl;//输出5
    int c=0;
    c=change(a);
    cout<<c<<endl;//输出10
}

为什么输出a=5呢？C语言中函数参数传递只能是值传递。a这个变量的值，传递给b(函数change的局部变量)，局部变量b被赋值成5。然后b这个变量 的内容，用10替换5，b就变成10。函数返回值是10。所以c被赋值为函数的返回值10。函数的返回值和对变量的修改没有关系。函数返回值只是函数的运 算结果。b并没有获得对a的修改权限。b和a是不同的两个变量，a只是把值的内容给了b，之后a和b没有关系。重要的一点是，如果要修改a的值，b必须获得对a的修改权限。

例子2 如何获得对调用者变量的修改权限？

#include <iostream>
using namespace std;
int change(int *b)
{
    *b=10;
    return *b;
}
int main()
{
    int a=5;
    int *p=&a;
    change(p);
    cout<<a<<endl;//输出10
　　 int c=0;
    c=change(p);
    cout<<c<<endl;//输出10
}

这个程序分为以下几步：

1、为int类型的变量a申请一片地址，初始化为5。（变量a的地址就不再变化了）

2、创建一个指向int类型的指针p，初始化为指向a（p的值是变量a的地址）。

3、为函数chang创建一个指向int类型的指针b。

4、把p的值给b（因为p和b指向的类型都是int，两者兼容，可以直接赋值）。这样b也指向a了（因为变量a的地址唯一，b的内容也是a的地址）

5、把b指向的内容修改成10。（也就是a被修改成10）

6、函数返回10，赋值给c。

由例1和例2总结出：若要通过函数B修改函数A中的某个变量a。需要获得变量a的地址，如果a是普通变量，需要获得一级指针。如果a是指针，需要获得二级指针。重点是看需要修改的变量是什么，再去获得它的指针。

例3 理解地址

#include <iostream>
using namespace std;
int main()
{
    int *str= NULL;
    int **p=NULL;
    p=&str;
    cout<<str<<endl;
    cout<<p<<endl;
}

输出：

0

0x61fe98

p->str->NULL

(int **->int*->int)

NULL是一个宏，#define NULL (void*)0，在C++里面被直接被定义成了整数立即数类型的0。

任何变量都会被分配内存空间。str指向的是NULL，那么str的值就是NULL的地址（NULL的地址被宏定义为0）。但是str在内存中也是有地址的，p的值是str的地址（这里是0x61fe98）。

例4 内存分配 

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
void GetMemory( int *p )
{
    p = (int *) malloc( 100 );
    cout<<p<<endl;
}
int main()
{
    int *str = NULL;
    GetMemory(str);
    cout<<str;
    return 0;
}

输出

0x12125f8

0

p的值最初被初始化为0，进行p = (int *) malloc( 100 ); 之后，p的值是内存随机分配的100个字节地址的首地址。str的值还是0。

对程序进行修改：

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
void GetMemory( int **p )
{
    *p = (int *) malloc( 100 );
}
int main()
{
    int *str = NULL;
    int **p2=&str; //等价于int **p2; p2=&str;
    GetMemory(p2);
    cout<<str;
    return 0;
}

输出

0xe425f8

在main中定义一个指向str的指针p2。把str的地址传给p。这样GetMemory函数中的p也指向str（因为变量str的地址是唯一的！），这样操作*p也就是操作str。

例5 最后看一道牛客网上的一道题http://www.nowcoder.com/profile/826954/myFollowings/detail/1002396 

void GetMemory( char *p )
{
 　　p = (char *) malloc( 100 ); //申请100个字节的存放char类型的连续区域
}
void Test( void )
{
 　　char *str = NULL;
 　　GetMemory( str );
 　　strcpy( str, "hello world" );
 　　printf( str );
}

这道题答案是str是NULL，如果在main中调用Test，运行会出错。分析一下：

1、Test中，创建一个指向char类型的指针str，str被初始化为0。

2、函数Test中执行GetMemory( str );

3、创建一个指向char类型的指针p。

4、把str的值（这里是0）传给p，指针变量p的值也被初始化成0。

5、把申请到的100个字节的内存强制转换成存放char类型，把所分配内存空间的首地址赋值给p（这时p的值从0变成某地址）。

但是这时候str还是指向NULL。

回到例1说的：若要通过函数GetMemory修改函数Test中的变量str，需要获得变量str的地址，而不是str的值。

PS:

C语言中的malloc函数（没有C++中new好用啊）：

malloc 函数 void *malloc( unsigned int size)

在内存的动态存储区中分配一块长度为"size" 字节的连续区域。

如果分配成功，则返回所分配内存空间的首地址，否则返回NULL，申请的内存不会进行初始化。

类型说明符表示把该区域用于何种数据类型。(类型说明符*)表示把返回值强制转换为该类型指针。例如： pc=(char *) malloc (100); 

二、二叉树的创建为什么用二级指针

感谢http://lidawn.github.io/pointer-on-pointer/这篇博客。这篇文章，概括一下：

调用者的变量需要被修改内容，这里是root（指向BTreeNode类型的指针），root需要指向一个新插入的节点，也就是需要修改root的值。所以 应该传入指向root的地址。这样在被调用的函数中，对*BST的操作等价于操作root。否则BST如果是和root类型一样的BTreeNode类型 的指针，BST和root位于两个不同的内存，BST只是被初始化为root的值，之后对BST的操作不会影响root。 

//以下代码来自《大话数据结构》6.9节
//二叉树的二叉链表结点结构定义
define char TElemType
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//为BiTNode取别名BiTNode，为BiTNode*取别名BiTree

void CreateBiTree(BiTree *T)//操作*T即可，*T是指向BiTNode的指针
{
    TElemType ch;
    scanf("%c",&ch);
    if(ch=='#')
        *T=NULL;
    else
    {
        *T=(BiTNode*)malloc(sizeof(BiTNode));
        //这里原来是*T=(BiTree)malloc(sizeof(BiTNode));修改之后便于理解
        if(!=*T)
            exit(OVERFLOW);
        //我理解是如果*T还是0(相当于*T还是指向NULL)，表示内存分配失败，就退出
        (*T)->data=ch;//*T指向的节点的data分配内容，即生成根节点
        CreateBiTree(&(*T)->lchild);//创建&(*T)->lchild临时变量，传入CreateBiTree，构造左子树
        CreateBiTree(&(*T)->rchild);//创建&(*T)->rchild临时变量，传入CreateBiTree，构造右子树
        //相当于
        // BiTNode **p1;  
        // p1=&((*T)->lchild);//不能直接p1=&lchild
        // CreateBiTree(p1);
        // BiTNode **p2;  
        // p2=&((*T)->rchild);//不能直接p2=&rchild
        // CreateBiTree(p2);
    }
}
操作*T相当于操作双亲节点的lchild或rchild（lchild或rchild的地址作为实参传递给形参T）
对于树根，没有双亲，最初传给T的就是NULL。
函数递归本质也是函数调用，之所以CreateBiTree(&(*T)->lchild) ，是因为要传当前节点的lchild(*T)->lchild的地址&(*T)->lchild给被调用者CreateBiTree。 
这里很重要的是：T是BiTNode**类型。是为了考虑函数的调用者。比如在main中要调用CreateBiTree函数。
 
如果CreateBiTree用BiTNode*类型的形参
void CreateBiTree(BiTNode *T){......}

int main(){

    struct BiTNode *p=NULL;

    CreateBiTree(p);

}
这样T会指向一棵二叉树，但是p还是指向NULL。
 
所以应该传入二级指针
void CreateBiTree(BiTNode **T){......}

int main(){

    struct BiTNode **p=NULL;

    struct BiTNode *b=NULL;

    p=&b;

    CreateBiTree(p);

}
这样操作*T也就是操作main中的b。最后b也会指向一棵二叉树。
 
或者也可以返回指针
BiTNode * CreateBiTree(BiTNode *T)
{
    ......
    return T;
}
int main(){
    struct BiTNode *p=NULL;
    p=CreateBiTree(p);
}
把T（最终指向创建好的二叉树的树根，树根的类型也是BiTNode ）， 返回给BiTNode *类型的p。这样p也指向创建好的二叉树的树根。
------------------------------------------------- 原创博客 转载请注明出处http://www.cnblogs.com/hslzju -------------------------------------------------
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/hslzju/p/5396987.html