一、为什么二叉树的根结点常常是指向指针的指针

因为在创造一颗树时，在申请根结点空间时，地址可能会发生变化，而这种变化是无法判断的，是系统自动发生的，单个指针就无法找到变化后的地址，所以 ，用指针的指针，找到变化后的地址。当然 如果你在创造一颗树前，就已经初始化分配了根结点的空间，那就不用指针的指针，直接用一个指针就行了。

它是一种C语言式的标准做法。

节点需要两重指针，一重是节点本身动态更改数据的需要，另一重是分配与操作堆内存数据的需要。

至于是不是一定要做成指针的指针形式，取决于节点数据是直接手动管理内存，这种可以指针的指针，效率较高。还是封装为某个结构的内部成员变量，开销略大一点，就只是指针的形式，好控制，使用方便。用智能指针的话，实际也是属于后者。

二叉树的建立中：

t=(BiTtree*)malloc(sizeof(BiTtree)); t->data=d; CreateBiTree(t->left,x); CreateBiTree(t->right,x);;

其中t=(tree*)malloc(sizeof(tree));

改变了指针的指向所以指针的指针，或者指针的引用

void CreateBiTree(BiTtree *&t,char x)

1

附上代码

#include

using namespace std;

struct BiTtree{

    char data;

    BiTtree *left,*right;

};

void CreateBiTree(BiTtree *&t,char x){

//在函数调用时用指针或者引用做参数，表示把变量的地址传递给子函数，

//但是子函数只能修改指针所指变量的值，并不能修改指针的指向。

//如果想要修改指针的指向，就要用指针的指针，或者指针的引用。

    char d;

    scanf(“%c”,&d);

    if(d==x){

       t=NULL;

    }

    else{

       t=(BiTtree*)malloc(sizeof(BiTtree));

       t->data=d;

       CreateBiTree(t->left,x);

       CreateBiTree(t->right,x);

    }

}

void printtree(BiTtree *t){

    if(t){

       printf(“%c “, t->data);

       printtree(t->left);

       printtree(t->right);

    }

}

int main(){

    BiTtree *t;

    CreateBiTree(t,’#’);

    printtree(t);

    return 0;

}

延伸阅读：

二、树

树（Tree）是n(n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树中：

此外，树的定义还需要强调以下两点：

上一篇

G1收集器的记忆集为什么选择用哈希表，为什么会选择双向的卡表结构来实现?

下一篇

HashMap为什么不用B+树来替换红黑树?