【正文】 例如 ,已知中序序列為 DGBAECF,后序序列為GDBEFCA。對(duì)應(yīng)的構(gòu)造二叉樹的過(guò)程如下所示。 根結(jié)點(diǎn)： A 左中序 :DGB 左根 :B 右中序 :ECF 右根 :C 根結(jié)點(diǎn)： B 左中序 :DG 左根 :D 右中序 :空 右根 :空 根結(jié)點(diǎn)： D 左中序 :空 左根 :空 右中序 :G 右根 :G 根結(jié)點(diǎn)： G 左中序 :空 左根 :空 右中序 :空 右根 :空 根結(jié)點(diǎn)： C 左中序 :E 左根 :E 右中序 :F 右根 :F 根結(jié)點(diǎn)： E 左中序 :空 左根 :空 右中序 :空 右根 :空 根結(jié)點(diǎn)： F 左中序 :空 左根 :空 右中序 :空 右根 :空 由上述定理得到以下構(gòu)造二叉樹的算法： BTNode *CreateBT2(char *post,char *in,int n,int m) { BTNode *s。char *p,*q,*maxp。int maxpost,maxin,k。 if (n=0) return NULL。 maxpost=1。 for (p=in。pin+n。p++) /*求 in在 post中最右邊的那個(gè)字符 */ for (q=post。qpost+m。q++) /*在 in中用 maxp指向這個(gè)字符 ,用 maxin標(biāo)識(shí)它在 in中的下標(biāo) */ if (*p==*q) { k=qpost。 if (kmaxpost) { maxpost=k。 maxp=p。 maxin=pin。 } } s=(BTNode *)malloc(sizeof(BTNode))。 /*創(chuàng)建二叉樹結(jié)點(diǎn) *s*/ sdata=post[maxpost]。 slchild=CreateBT2(post,in,maxin,m)。 /*遞歸構(gòu)造左子樹 */ srchild=CreateBT2(post,maxp+1,nmaxin1,m)。 /*遞歸構(gòu)造右子樹 */ return s。 } 線索二叉樹 線索二叉樹的概念 對(duì)于具有 n個(gè)結(jié)點(diǎn)的二叉樹 ,采用二叉鏈存儲(chǔ)結(jié)構(gòu)時(shí) ,每個(gè)結(jié)點(diǎn)有兩個(gè)指針域 ,總共有 2n個(gè)指針域 ,又由于只有 n1個(gè)結(jié)點(diǎn)被有效指針?biāo)赶?(n個(gè)結(jié)點(diǎn)中只有樹根結(jié)點(diǎn)沒有被有效指針域所指向 ),則共有 2n(n1)=n+1個(gè)空鏈域 , 我們知道 ,遍歷二叉樹的結(jié)果是一個(gè)結(jié)點(diǎn)的線性序列 。 可以利用這些空鏈域存放指向結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn)的指針 。 這樣的指向該線性序列中的 “ 前驅(qū) ” 和 “ 后繼 ” 的指針 ,稱作線索 。 在結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)上增加兩個(gè)標(biāo)志位來(lái)區(qū)分這兩種情況： 左標(biāo)志 ltag : 0 表示 lchild指向左孩子結(jié)點(diǎn) 1 表示 lchild指向前驅(qū)結(jié)點(diǎn) 右標(biāo)志 rtag : 0 表示 rchild指向右孩子結(jié)點(diǎn) 1 表示 rchild指向后繼結(jié)點(diǎn) 這樣 ,每個(gè)結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)如下： ltag child data rchild rtag 按上述原則在二叉樹的每個(gè)結(jié)點(diǎn)上加上線索的二叉樹稱作 線索二叉樹 。 對(duì)二叉樹以某種方式遍歷使其變?yōu)榫€索二叉樹的過(guò)程稱作按該方式對(duì)二叉樹進(jìn)行 線索化 。 為使算法設(shè)計(jì)方便 ,在線索二叉樹中再增加一個(gè)頭結(jié)點(diǎn)。頭結(jié)點(diǎn)的 data域?yàn)榭眨?lchild指向無(wú)線索時(shí)的根結(jié)點(diǎn) ,ltag為 0； rchild指向按某種方式遍歷二叉樹時(shí)的最后一個(gè)結(jié)點(diǎn) ,rtag為 1。 教材中圖 (a)所示二叉樹的線索二叉樹。其中 ,圖 (a)是中序線索二叉樹 (中序序列為：DGBAECF),圖 (b)是先序線索二叉樹 (先序序列為：ABDGCEF),圖 (c)是后序線索二叉樹 (后序序列為：GDBEFCA)。圖中實(shí)線表示二叉樹原來(lái)指針?biāo)傅慕Y(jié)點(diǎn) ,虛線表示線索二叉樹所添加的線索。 0 1 0 A 0 0 B 1 0 C 0 1 E 1 1 F 1 1 D 0 1 G 1 0 1 0 A 0 0 B 1 0 C 0 1 E 1 1 F 1 1 D 0 1 G 1 ro o t ro o t 0 1 0 A 0 0 B 1 0 C 0 1 E 1 1 F 1 1 D 0 1 G 1 ro o t (a ) 中序線索樹 (b ) 先序線索樹 (c ) 后序線索樹 線索化二叉樹 建立線索二叉樹 ,或者說(shuō) ,對(duì)二叉樹線索化 ,實(shí)質(zhì)上就是遍歷一棵二叉樹 ,在遍歷的過(guò)程中 ,檢查當(dāng)前結(jié)點(diǎn)的左 、右指針域是否為空 。 如果為空 ,將它們改為指向前驅(qū)結(jié)點(diǎn)或后繼結(jié)點(diǎn)的線索 。 另外 ,在對(duì)一棵二叉樹添加線索時(shí) ,我們創(chuàng)建一個(gè)頭結(jié)點(diǎn) ,并建立頭結(jié)點(diǎn)與二叉樹的根結(jié)點(diǎn)的線索 。 對(duì)二叉樹線索化后 ,還須建立最后一個(gè)結(jié)點(diǎn)與頭結(jié)點(diǎn)之間的線索 。 下面以中序線索二叉樹為例 ,討論建立線索二叉樹的算法 。 為了實(shí)現(xiàn)線索化二叉樹 ,將前面二叉樹結(jié)點(diǎn)的類型定義修改如下： typedef struct node { ElemType data。 /*結(jié)點(diǎn)數(shù)據(jù)域 */ int ltag,rtag。 /*增加的線索標(biāo)記 */ struct node *lchild。 /*左孩子或線索指針 */ struct node *rchild。 /*右孩子或線索指針 */ } TBTNode。 /*線索樹結(jié)點(diǎn)類型定義 */ 下 面 是 建 立 中 序 線 索 二 叉 樹 的 算 法 。CreaThread(b)算法是將以二叉鏈存儲(chǔ)的二叉樹 b進(jìn)行中序線索化 ,并返回線索化后頭結(jié)點(diǎn)的指針 root。Thread(p)算法用于對(duì)于以 *p為根結(jié)點(diǎn)的二叉樹中序線索化 。 在整個(gè)算法中 p總是指向當(dāng)前被線索化的結(jié)點(diǎn) ,而pre作為全局變量 ,指向剛剛訪問(wèn)過(guò)的結(jié)點(diǎn) ,*pre是 *p的前驅(qū)結(jié)點(diǎn) ,*p是 *pre的后繼結(jié)點(diǎn) 。 CreaThread(b)算法思路是：先創(chuàng)建頭結(jié)點(diǎn) *root,其 lchild域?yàn)榫€索 ,rchild域?yàn)殒溨羔?。?rchild指針指向 *b,如果 b二叉樹為空 ,則將其 lchild指向自身。否則將*root的 lchild指向 *b結(jié)點(diǎn) ,p指向 *b結(jié)點(diǎn) ,pre指向 *root結(jié)點(diǎn)。再調(diào)用 Thread(b)對(duì)整個(gè)二叉樹線索化。最后加入指向頭結(jié)點(diǎn)的線索 ,并將頭結(jié)點(diǎn)的 rchild指針域線索化為指向最后一個(gè)結(jié)點(diǎn) (由于線索化直到 p等于 NULL為止 ,所以最后一個(gè)結(jié)點(diǎn)為 *pre)。 TBTNode *CreaThread(TBTNode *b) /*中序線索化二叉樹 */ { TBTNode *root。 root=(TBTNode *)malloc(sizeof(TBTNode))。 /*創(chuàng)建頭結(jié)點(diǎn) */ rootltag=0。rootrtag=1。 rootrchild=b。 if (b==NULL) rootlchild=root。 /*空二叉樹 */ else { rootlchild=b。 pre=root。 /*pre是 *p的前驅(qū)結(jié)點(diǎn) ,供加線索用 */ Thread(b)。 /*中序遍歷線索化二叉樹 */ prerchild=root。 /*最后處理 ,加入指向頭結(jié)點(diǎn)的線索 */ prertag=1。 rootrchild=pre。 /*頭結(jié)點(diǎn)右線索化 */ } return root。 } Thread(p)算法思路是：類似于中序遍歷的遞歸算法 ,在 p指針不為 NULL時(shí) ,先對(duì) *p結(jié)點(diǎn)的左子樹線索化；若 *p結(jié)點(diǎn)沒有左孩子結(jié)點(diǎn) ,則將其 lchild指針線索化為指向其前驅(qū)結(jié)點(diǎn) *pre,否則表示 lchild指向其左孩子結(jié)點(diǎn) ,將其 ltag置為 1；若 *pre結(jié)點(diǎn)的 rchild指針為 NULL,將其 rchild指針線索化為指向其后繼結(jié)點(diǎn) *p,否則 rchild表示指向其右孩子結(jié)點(diǎn) ,將其 rtag置為 1,再將 pre指向 *p；最后對(duì) *p結(jié)點(diǎn)的右子樹線索化 。 TBTNode *pre。 /*全局變量 */ void Thread(TBTNode *amp。p) /*對(duì)二叉樹 b進(jìn)行中序線索化 */ { if (p!=NULL) { Thread(plchild)。 /*左子樹線索化 */ if (plchild==NULL) /*前驅(qū)線索 */ { plchild=pre。 pltag=1。} /*建立當(dāng)前結(jié)點(diǎn)的前驅(qū)線索 */ else pltag=0。 if (prerchild==NULL) /*后繼線索 */ { prerchild=p。prertag=1。}/*建立前驅(qū)結(jié)點(diǎn)的后繼線索 */ else prertag=0。 pre=p。 Thread(prchild)。 /*遞歸調(diào)用右子樹線索化 */ } } 中序遍歷 (遞歸 ) 遍歷線索化二叉樹 遍歷某種次序的線索二叉樹 ,就是從該次序下的開始結(jié)點(diǎn)出發(fā) ,反復(fù)找到該結(jié)點(diǎn)在該次序下的后繼結(jié)點(diǎn) ,直到終端結(jié)點(diǎn)。 在中序線索二叉樹中 ,開始結(jié)點(diǎn)就是根結(jié)點(diǎn)的最左下結(jié)點(diǎn) ,而求當(dāng)前結(jié)點(diǎn)在中序序列下的后繼和前驅(qū)結(jié)點(diǎn)的方法如教材中表 ,最后一個(gè)結(jié)點(diǎn)的 rchild指針被線索化為指向頭結(jié)點(diǎn)。利用這些條件 ,在中序線索化二叉樹中實(shí)現(xiàn)中序遍歷的算法如下： void ThInOrder(TBTNode *tb) { TBTNode *p=tblchild。 /*p指向根結(jié)點(diǎn) */ while (p!=tb) { while (pltag==0) p=plchild。 /*找開始結(jié)點(diǎn) */ printf(%c,pdata)。 /*訪問(wèn)開始結(jié)點(diǎn) */ while (prtag==1 amp。amp。 prchild!=tb) { p=prchild。 printf(%c,pdata)。 } p=prchild。 } } 哈夫曼樹 哈夫曼樹的定義 構(gòu)造哈夫曼樹 哈夫曼編碼 哈夫曼樹的定義 設(shè)二叉樹具有 n個(gè)帶權(quán)值的葉子結(jié)點(diǎn) ,那么從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度與相應(yīng)結(jié)點(diǎn)權(quán)值的乘積的和 ,叫做二叉樹的帶權(quán)路徑長(zhǎng)度 。 其中 ,n表示葉子結(jié)點(diǎn)的數(shù)目 ,wi和 li分別表示葉子結(jié)點(diǎn) ki的權(quán)值和根到 ki之間的路徑長(zhǎng)度 (即從葉子結(jié)點(diǎn)到達(dá)根結(jié)點(diǎn)的分支數(shù) )。 具有最小帶權(quán)路徑長(zhǎng)度的二叉樹稱為哈夫曼樹 。 ???niii lwW P L1 構(gòu)造哈夫曼樹 根據(jù)哈夫曼樹的定義 ,一棵二叉樹要使其 WPL值最小 ,必須使權(quán)值越大的葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn) ,而權(quán)值越小的葉子結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn) 。 那么如何構(gòu)造一棵哈夫曼樹呢 ?其方法如下 : (1)由給定的 n個(gè)權(quán)值 {W1,W2,...,Wn}構(gòu)造 n棵只有一個(gè)葉子結(jié)點(diǎn)的二叉樹 ,從而得到一個(gè)二叉樹的集合F={T1,T2,...,Tn}。 (2)在 F中選取根結(jié)點(diǎn)的權(quán)值最小和次小的兩棵二叉樹作為左 、 右子樹構(gòu)造一棵新的二叉樹 ,這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左 、 右子樹根結(jié)點(diǎn)權(quán)值之和 。 (3)在集合 F中刪除作為左 、 右子樹的兩棵二叉樹 ,并將新建立的二叉樹加入到集合 F中 。 (4)重復(fù) (2)、 (3)兩步 ,當(dāng) F中只剩下一棵二叉樹時(shí) ,這棵二叉樹便是所要建立的哈夫曼樹 。 給定權(quán)值 w=(1,3,5,7)來(lái)構(gòu)造一棵哈夫曼樹 。 9 4 1 7 5 3 16 9 4 1 7