[C++知识库]使用一级/二级指针创建二叉树（两种角度详解二叉树建立及二级指针）

二级指针是什么？？？

可以先通过以下代码感知一下二级指针是什么？

int main(){
    int arr[5] = {1, 2, 3, 4, 5};
    int* parr = &arr[0];   //也可以直接写数组名arr
    int* *pparr = &parr;   //二级指针,指针的指针,一般希望修改函数中的指针时会用到
    printf("%d\n", *(arr + 3));  //arr[3]
    printf("%d\n", *(*pparr + 3));  //(*ppar)[3]
    return 0;
}

平时见到的（一级）指针是普通变量的指针，而这里的二级指针就是一级指针的指针。

如上图所示，a为普通变量，p1为指向a的指针，p2为指向p1的指针，也就是我们关注的二级指针。

二叉树的创建

请着重关注下列代码中

• A.先序建立二叉树（无返回值版本） 及主函数中二级指针版二叉树构造方法
• B.先序建立二叉树（有返回值版） 及主函数中一级指针版二叉树构造方法

请仔细对比A和B段代码的区别，并实际运行以下，你将收获匪浅。

#include <stdio.h>
#include <malloc.h>

typedef char BiElemType;
typedef struct BTNode{
    BiElemType data;  //数据域
    struct BTNode * pLchild;
    struct BTNode * pRchild;
}BTNode, * BiTree;

/*
使用二级指针的原因：
1.若要通过函数B修改函数A中的某个变量a。需要获得变量a的地址，如果
a是普通变量，需要获得一级指针。如果a是指针，需要获得二级指针。
2.root需要指向一个新插入的节点，也就是需要修改root的值。所以 应该传入指向root的地址。
3.如果仅使用一级指针，那么只能改变形参的内存，如，root = malloc(sizeof(struct TreeNode)); 
这个root和函数外的实参的内存空间不同，所以修改它并不会对实参的内存造成影响，
所以必须把它做为返回值返回去，否则函数外就没法获得这个变化的值。
*/

/*
A.先序建立二叉树（无返回值版本）
需要在main函数中定义一个根节点
注意这是个二叉树节点的指针类型;然后将这个参数
传递给一个CreateBTree函数;在该函数中递归创建二叉树
*/
void CreateBTree(BiTree * root){  //二级指针(BiTree本身就是指针)
    char c;
    scanf("%c", &c);  //接受一个字符
    if(c == '#'){  //遇到#
        *root = NULL;  //将此节点置为空
    }else{  //从函数外部接受root(二级指针的形式)并在函数内部进行修改
        (*root) = (BiTree)malloc(sizeof(BTNode));  //创建一个新的节点
        (*root)->data = c;
        CreateBTree(&(*root)->pLchild);   //沿左子树继续创建
        CreateBTree(&(*root)->pRchild);   //沿右子树继续创建
    }
    
}

/*
B.先序建立二叉树（有返回值版）
可以直接在CreatBiTree函数中创建二叉树，并返回二叉树的根指针
*/
BiTree CreateBTree2(){
    char c;
    BiTree root = NULL;  //在函数内部创建root
    scanf("%c", &c);  //接受一个字符
    if(c == '#'){  //遇到#
        root = NULL;  //将此节点置为空
        return NULL; //必须return NULL
    }else{
        root = (BiTree)malloc(sizeof(BTNode));  //创建一个新的节点
        root->data = c;
        root->pLchild = CreateBTree2();   //沿左子树继续创建
        root->pRchild = CreateBTree2();   //沿右子树继续创建
        return root;
    }
}

//先序遍历二叉树
void PreOrderTraverse(BiTree root){
    if(root != NULL){
        printf("%c", root->data);
        PreOrderTraverse(root->pLchild);
        PreOrderTraverse(root->pRchild);
    }else{
        printf("#");
    }
}

int main(){
    //A.二级指针构造方式
    BiTree root = NULL;
    CreateBTree(&root);
    PreOrderTraverse(root);
    //B.一级指针构造方式
    BiTree root = CreateBTree2();
    PreOrderTraverse(root);
    return 0;
}