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

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

它是一種C語(yǔ)言式的標(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)部成員變量，開(kāi)銷略大一點(diǎn)，就只是指針的形式，好控制，使用方便。用智能指針的話，實(shí)際也是屬于后者。

二叉樹(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;

}

延伸閱讀：

二、樹(shù)

樹(shù)（Tree）是n(n>=0)個(gè)結(jié)點(diǎn)的有限集。n=0時(shí)稱為空樹(shù)。在任意一顆非空樹(shù)中：

有且僅有一個(gè)特定的稱為根（Root）的結(jié)點(diǎn)；當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1、T2、…… 為什么二叉樹(shù)的根結(jié)點(diǎn)常常是指向指針的指針Tn，其中每一個(gè)集合本身又是一棵樹(shù)，并且稱為根的子樹(shù)。

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

n>0時(shí)根結(jié)點(diǎn)是少數(shù)的，不可能存在多個(gè)根結(jié)點(diǎn)，數(shù)據(jù)結(jié)構(gòu)中的樹(shù)只能有一個(gè)根結(jié)點(diǎn)。m>0時(shí)，子樹(shù)的個(gè)數(shù)沒(méi)有限制，但它們一定是互不相交的。