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

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

它是一種C語言式的標(biāo)準(zhǔn)做法。

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

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

二叉樹的建立中：

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ù)，

//但是子函數(shù)只能修改指針?biāo)缸兞康闹担⒉荒苄薷闹羔樀闹赶颉?/p>

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

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

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