一、為什么二叉樹的根結(jié)點(diǎn)常常是指向指針的指針
因?yàn)樵趧?chuàng)造一顆樹時(shí),在申請(qǐng)根結(jié)點(diǎn)空間時(shí),地址可能會(huì)發(fā)生變化,而這種變化是無(wú)法判斷的,是系統(tǒng)自動(dòng)發(fā)生的,單個(gè)指針就無(wú)法找到變化后的地址,所以 ,用指針的指針,找到變化后的地址。當(dāng)然 如果你在創(chuàng)造一顆樹前,就已經(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)部成員變量,開銷略大一點(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í)稱為空樹。在任意一顆非空樹中:
有且僅有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn);當(dāng)n>1時(shí),其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1、T2、…… 為什么二叉樹的根結(jié)點(diǎn)常常是指向指針的指針Tn,其中每一個(gè)集合本身又是一棵樹,并且稱為根的子樹。此外,樹的定義還需要強(qiáng)調(diào)以下兩點(diǎn):
n>0時(shí)根結(jié)點(diǎn)是少數(shù)的,不可能存在多個(gè)根結(jié)點(diǎn),數(shù)據(jù)結(jié)構(gòu)中的樹只能有一個(gè)根結(jié)點(diǎn)。m>0時(shí),子樹的個(gè)數(shù)沒(méi)有限制,但它們一定是互不相交的。