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