第11講第六章樹(四)6.7線索二叉樹6.7.1線索二叉樹的概念對于具有n個結(jié)點的二叉樹,采用二叉鏈存儲結(jié)構(gòu)時,每個結(jié)點有兩個指針域,總共有2n個指針域,又由于只有n-1個結(jié)點被有效指針所指向(n個結(jié)點中只有樹根結(jié)點沒有被有效指針域所指向),則共有2n-(n-1)=n+1個空鏈域,我們知道,遍歷二叉樹的結(jié)果是一個結(jié)點的線性序列。可以利用這些空鏈域存放指向結(jié)點的前驅(qū)和后繼結(jié)點的指針。這樣的指向該線性序列中的“前驅(qū)”和“后繼”的指針,稱作線索。在結(jié)點的存儲結(jié)構(gòu)上增加兩個標志位來區(qū)分這兩種情況：左標志ltag:0表示lchild指向左孩子結(jié)點1表示lchild指向前驅(qū)結(jié)點右標志rtag:0表示rchild指向右孩子結(jié)點1表示rchild指向后繼結(jié)點這樣,每個結(jié)點的存儲結(jié)構(gòu)如下：ltaglchilddatarchildrtag按上述原則在二叉樹的每個結(jié)點上加上線索的二叉樹稱作線索二叉樹。對二叉樹以某種方式遍歷使其變?yōu)榫€索二叉樹的過程稱作按該方式對二叉樹進行線索化。為使算法設(shè)計方便,在線索二叉樹中再增加一個頭結(jié)點。頭結(jié)點的data域為空；lchild指向無線索時的根結(jié)點,ltag為0；rchild指向按某種方式遍歷二叉樹時的最后一個結(jié)點,rtag為1。

Thread(b); /*中序遍歷線索化二叉樹*/pre=p;structnode*rchild; /*右孩子或線索指針*/lchild=ht[i].對于具有n個結(jié)點的二叉樹,采用二叉鏈存儲結(jié)構(gòu)時,每個結(jié)點有兩個指針域,總共有2n個指針域,又由于只有n-1個結(jié)點被有效指針所指向(n個結(jié)點中只有樹根結(jié)點沒有被有效指針域所指向),則共有2n-(n-1)=n+1個空鏈域,這樣的指向該線性序列中的“前驅(qū)”和“后繼”的指針,稱作線索。elsepre->rtag=0;voidThInOrder(TBTNode*tb)lchild指向無線索時的根結(jié)點,ltag為0；pre=root; /*pre是*p的前驅(qū)結(jié)點,供加線索用*/再調(diào)用Thread(b)對整個二叉樹線索化。while(f!=-1)/*循環(huán)直到無雙親結(jié)點即到達樹根結(jié)點*/lchild=ht[i].ht[lnode].{min2=ht[k].(4)重復(fù)(2)、(3)兩步,當F中只剩下一棵二叉樹時,這棵二叉樹便是所要建立的哈夫曼樹。6.7.2線索化二叉樹建立線索二叉樹,或者說,對二叉樹線索化,實質(zhì)上就是遍歷一棵二叉樹,在遍歷的過程中,檢查當前結(jié)點的左、右指針域是否為空。如果為空,將它們改為指向前驅(qū)結(jié)點或后繼結(jié)點的線索。另外,在對一棵二叉樹添加線索時,我們創(chuàng)建一個頭結(jié)點,并建立頭結(jié)點與二叉樹的根結(jié)點的線索。對二叉樹線索化后,還須建立最后一個結(jié)點與頭結(jié)點之間的線索。下面以中序線索二叉樹為例,討論建立線索二叉樹的算法。為了實現(xiàn)線索化二叉樹,將前面二叉樹結(jié)點的類型定義修改如下：typedefstructnode{ElemTypedata; /*結(jié)點數(shù)據(jù)域*/intltag,rtag; /*增加的線索標記*/structnode*lchild; /*左孩子或線索指針*/structnode*rchild; /*右孩子或線索指針*/}TBTNode; /*線索樹結(jié)點類型定義*/下面是建立中序線索二叉樹的算法。CreaThread(b)算法是將以二叉鏈存儲的二叉樹b進行中序線索化,并返回線索化后頭結(jié)點的指針root。Thread(p)算法用于對于以*p為根結(jié)點的二叉樹中序線索化。在整個算法中p總是指向當前被線索化的結(jié)點,而pre作為全局變量,指向剛剛訪問過的結(jié)點,*pre是*p的前驅(qū)結(jié)點,*p是*pre的后繼結(jié)點。

CreaThread(b)算法思路是：先創(chuàng)建頭結(jié)點*root,其lchild域為線索,rchild域為鏈指針。將rchild指針指向*b,如果b二叉樹為空,則將其lchild指向自身。否則將*root的lchild指向*b結(jié)點,p指向*b結(jié)點,pre指向*root結(jié)點。再調(diào)用Thread(b)對整個二叉樹線索化。最后加入指向頭結(jié)點的線索,并將頭結(jié)點的rchild指針域線索化為指向最后一個結(jié)點(由于線索化直到p等于NULL為止,所以最后一個結(jié)點為*pre)。TBTNode*CreaThread(TBTNode*b)/*中序線索化二叉樹*/{TBTNode*root;root=(TBTNode*)malloc(sizeof(TBTNode));/*創(chuàng)建頭結(jié)點*/root->ltag=0;root->rtag=1;root->rchild=b;if(b==NULL)root->lchild=root; /*空二叉樹*/else{root->lchild=b; pre=root; /*pre是*p的前驅(qū)結(jié)點,供加線索用*/ Thread(b); /*中序遍歷線索化二叉樹*/ pre->rchild=root; /*最后處理,加入指向頭結(jié)點的線索*/ pre->rtag=1; root->rchild=pre; /*頭結(jié)點右線索化*/}returnroot;}Thread(p)算法思路是：類似于中序遍歷的遞歸算法,在p指針不為NULL時,先對*p結(jié)點的左子樹線索化；若*p結(jié)點沒有左孩子結(jié)點,則將其lchild指針線索化為指向其前驅(qū)結(jié)點*pre,否則表示lchild指向其左孩子結(jié)點,將其ltag置為1；若*pre結(jié)點的rchild指針為NULL,將其rchild指針線索化為指向其后繼結(jié)點*p,否則rchild表示指向其右孩子結(jié)點,將其rtag置為1,再將pre指向*p；最后對*p結(jié)點的右子樹線索化。TBTNode*pre; /*全局變量*/voidThread(TBTNode*&p)/*對二叉樹b進行中序線索化*/{if(p!=NULL) {Thread(p->lchild); /*左子樹線索化*/ if(p->lchild==NULL)/*前驅(qū)線索*/ {p->lchild=pre;p->ltag=1;}/*建立當前結(jié)點的前驅(qū)線索*/ elsep->ltag=0; if(pre->rchild==NULL) /*后繼線索*/ {pre->rchild=p;pre->rtag=1;}/*建立前驅(qū)結(jié)點的后繼線索*/ elsepre->rtag=0;pre=p; Thread(p->rchild); /*遞歸調(diào)用右子樹線索化*/}}中序遍歷(遞歸)6.7.3遍歷線索化二叉樹遍歷某種次序的線索二叉樹,就是從該次序下的開始結(jié)點出發(fā),反復(fù)找到該結(jié)點在該次序下的后繼結(jié)點,直到終端結(jié)點。在中序線索二叉樹中,開始結(jié)點就是根結(jié)點的最左下結(jié)點,最后一個結(jié)點的rchild指針被線索化為指向頭結(jié)點。利用這些條件,在中序線索化二叉樹中實現(xiàn)中序遍歷的算法如下：voidThInOrder(TBTNode*tb){TBTNode*p=tb->lchild; /*p指向根結(jié)點*/while(p!=tb){while(p->ltag==0)p=p->lchild; /*找開始結(jié)點*/ printf("%c",p->data); /*訪問開始結(jié)點*/ while(p->rtag==1&&p->rchild!=tb) {p=p->rchild; printf("%c",p->data); } p=p->rchild; }}打開一片英文文章，能統(tǒng)計該文章中每個字符出現(xiàn)的次數(shù)，然后以他們作為權(quán)值，對每一個字符進行編碼，編碼完成后再對其編碼進行譯碼。6.8哈夫曼樹6.8.1哈夫曼樹的定義設(shè)二叉樹具有n個帶權(quán)值的葉子結(jié)點,那么從根結(jié)點到各個葉子結(jié)點的路徑長度與相應(yīng)結(jié)點權(quán)值的乘積的和,叫做二叉樹的帶權(quán)路徑長度。其中,n表示葉子結(jié)點的數(shù)目,wi和li分別表示葉子結(jié)點ki的權(quán)值和根到ki之間的路徑長度(即從葉子結(jié)點到達根結(jié)點的分支數(shù))。具有最小帶權(quán)路徑長度的二叉樹稱為哈夫曼樹。

6.8.2構(gòu)造哈夫曼樹根據(jù)哈夫曼樹的定義,一棵二叉樹要使其WPL值最小,必須使權(quán)值越大的葉子結(jié)點越靠近根結(jié)點,而權(quán)值越小的葉子結(jié)點越遠離根結(jié)點。那么如何構(gòu)造一棵哈夫曼樹呢?其方法如下:(1)由給定的n個權(quán)值{W1,W2,...,Wn}構(gòu)造n棵只有一個葉子結(jié)點的二叉樹,從而得到一個二叉樹的集合F={T1,T2,...,Tn};(2)在F中選取根結(jié)點的權(quán)值最小和次小的兩棵二叉樹作為左、右子樹構(gòu)造一棵新的二叉樹,這棵新的二叉樹根結(jié)點的權(quán)值為其左、右子樹根結(jié)點權(quán)值之和;(3)在集合F中刪除作為左、右子樹的兩棵二叉樹,并將新建立的二叉樹加入到集合F中;(4)重復(fù)(2)、(3)兩步,當F中只剩下一棵二叉樹時,這棵二叉樹便是所要建立的哈夫曼樹。給定權(quán)值w=(1,3,5,7)來構(gòu)造一棵哈夫曼樹。構(gòu)造一棵哈夫曼樹的過程為了實現(xiàn)構(gòu)造哈夫曼樹的算法,設(shè)計哈夫曼樹中每個結(jié)點類型如下：typedefstruct{ chardata; /*結(jié)點值*/ floatweight; /*權(quán)重*/ intparent; /*雙親結(jié)點*/ intlchild; /*左孩子結(jié)點*/ intrchild; /*右孩子結(jié)點*/}HTNode;

用ht[]數(shù)組存放哈夫曼樹,對于具有n個葉子結(jié)點的哈夫曼樹,總共有2n-1個結(jié)點。其算法思路是：n個葉子結(jié)點只有data和weight域值,先將所有2n-1個結(jié)點的parent、lchild和rchild域置為初值-1。處理每個非葉子結(jié)點ht[i](存放在ht[n]～ht[2n-2]中)：從ht[0]～ht[i-2]中找出根結(jié)點(即其parent域為-1)最小的兩個結(jié)點ht[lnode]和ht[rnode],將它們作為ht[i]的左右子樹,ht[lnode]和ht[rnode]的雙親結(jié)點置為ht[i],并且ht[i].weight=ht[lnode].weight+ht[rnode].weight。如此這樣直到所有2n-1個非葉子結(jié)點處理完畢。構(gòu)造哈夫曼樹的算法如下：voidCreateHT(HTNodeht[],intn){ inti,j,k,lnode,rnode; floatmin1,min2; for(i=0;i<2*n-1;i++) /*所有結(jié)點的相關(guān)域置初值-1*/ ht[i].parent=ht[i].lchild=ht[i].rchild=-1; for(i=n;i<2*n-1;i++) /*構(gòu)造哈夫曼樹*/ {min1=min2=32767;lnode=rnode=-1; for(k=0;k<=i-1;k++) if(ht[k].parent==-1)/*未構(gòu)造二叉樹的結(jié)點中查找*/ {if(ht[k].weight<min1) {min2=min1;rnode=lnode; min1=ht[k].weight;lnode=k;} elseif(ht[k].weight<min2) {min2=ht[k].weight;rnode=k;}}/*if*/ ht[lnode].parent=i;ht[rnode].parent=i; ht[i].weight=ht[lnode].weight+ht[rnode].weight; ht[i].lchild=lnode;ht[i].rchild=rnode; }}具有最小帶權(quán)路徑長度的二叉樹稱為哈夫曼樹。}/*if*/structnode*rchild; /*右孩子或線索指針*/intrchild; /*右孩子結(jié)點*/{min1=min2=32767;lnode=rnode=-1;{ inti,f,c;HCodehc;parent;/*再對雙親結(jié)點進行同樣的操作*/{min2=min1;rnode=lnode;遍歷某種次序的線索二叉樹,就是從該次序下的開始結(jié)點出發(fā),反復(fù)找到該結(jié)點在該次序下的后繼結(jié)點,直到終端結(jié)點。根據(jù)哈夫曼樹求對應(yīng)的哈夫曼編碼的算法如下：(3)在集合F中刪除作為左、右子樹的兩棵二叉樹,并將新建立的二叉樹加入到集合F中;左標志ltag:0表示lchild指向左孩子結(jié)點下面是建立中序線索二叉樹的算法。root->ltag=0;root->rtag=1;root->rchild=b;如此這樣直到所有2n-1個非葉子結(jié)點處理完畢。intlchild; /*左孩子結(jié)點*/6.8.3哈夫曼編碼具體構(gòu)造方法如下：設(shè)需要編碼的字符集合為{d1,d2,…,dn},各個字符在電文中出現(xiàn)的次數(shù)集合為{w1,w2,…,wn},以d1,d2,…,dn作為葉結(jié)點,以w1,w2,…,wn作為各根結(jié)點到每個葉結(jié)點的權(quán)值構(gòu)造一棵二叉樹,規(guī)定哈夫曼樹中的左分支為0,右分支為1,則從根結(jié)點到每個葉結(jié)點所經(jīng)過的分支對應(yīng)的0和1組成的序列便為該結(jié)點對應(yīng)字符的編碼。這樣的編碼稱為哈夫曼編碼。對應(yīng)的哈夫曼編碼如下：1：0003：0015：017：1為了實現(xiàn)構(gòu)造哈夫曼編碼的算法,設(shè)計存放每個結(jié)點哈夫曼編碼的類型如下：typedefstruct