一、為什么二叉樹的根結(jié)點常常是指向指針的指針

因為在創(chuàng)造一顆樹時，在申請根結(jié)點空間時，地址可能會發(fā)生變化，而這種變化是無法判斷的，是系統(tǒng)自動發(fā)生的，單個指針就無法找到變化后的地址，所以 ，用指針的指針，找到變化后的地址。當然 如果你在創(chuàng)造一顆樹前，就已經(jīng)初始化分配了根結(jié)點的空間，那就不用指針的指針，直接用一個指針就行了。

它是一種C語言式的標準做法。

節(jié)點需要兩重指針，一重是節(jié)點本身動態(tài)更改數(shù)據(jù)的需要，另一重是分配與操作堆內(nèi)存數(shù)據(jù)的需要。

至于是不是一定要做成指針的指針形式，取決于節(jié)點數(shù)據(jù)是直接手動管理內(nèi)存，這種可以指針的指針，效率較高。還是封裝為某個結(jié)構的內(nèi)部成員變量，開銷略大一點，就只是指針的形式，好控制，使用方便。用智能指針的話，實際也是屬于后者。

二叉樹的建立中：

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){

//在函數(shù)調(diào)用時用指針或者引用做參數(shù)，表示把變量的地址傳遞給子函數(shù)，

//但是子函數(shù)只能修改指針所指變量的值，并不能修改指針的指向。

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

??? 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)個結(jié)點的有限集。n=0時稱為空樹。在任意一顆非空樹中：

此外，樹的定義還需要強調(diào)以下兩點：