【正文】 //輸 入葉子權(quán)值至 T[0．． n1]的 weight域 for(i=n。im。i++) { SelectMin(T,i1,amp。p1,amp。p2)。//共進 行 n1次合并，新結(jié)點依次存于 T[i]中 //在 T[0…i 1]中選擇兩個權(quán)最小的根結(jié)點，其序號分別為 p1和 p2 T[p1].parent=T[p2].parent=i。 T[i].1child=p1。 //最小權(quán)的根結(jié)點是新結(jié)點的左孩子 T[i].rchild=p2。 //次小權(quán)的根結(jié)點是新結(jié)點的右孩子 T[i].weight=T[p1].weight+T[p2].weight。 } } 【例 67】用鏈表構(gòu)造哈夫曼樹 【解】哈夫曼樹的鏈表結(jié)構(gòu)算法描述如下： include “” include “” include “” define m 100 struct ptree //定義二叉樹結(jié)點類型 { int w。 //定義結(jié)點權(quán)值 struct ptree *lchild。 //定義左子結(jié)點指針 struct ptree *rchild。 //定義右子結(jié)點指針 }。 struct pforest //定義鏈表結(jié)點類型 { struct pforest *link。 struct ptree *root。 }。 int WPL=0。 //初始化 WTL為 0 struct ptree *hafm()。 void travel()。 struct pforest *inforest()。 main( ) { struct ptree *head。 int n,i,w[m]。 printf(please input the sum of node\n)。 //提示輸入結(jié)點數(shù) scanf(%d,amp。n)。 //輸入結(jié)點數(shù) printf (please input weight of every node\n)。 //提示輸入每個結(jié)點的權(quán)值 for(i=1。i=n。i++) scanf(%d,amp。w[i])。 //輸入每個結(jié)點權(quán)值 head=hafm(w,n)。 travel(head,0)。 printf(The length of the best path is WPL=%d, WPL)。 //輸出最佳路徑權(quán)值之和 } void travel(struct ptree *head,int n) //為驗證 harfm算法的正確性進行的遍歷 { struct ptree *p。 p=head。 if(p!=NULL) { if((plchild)==NULL amp。amp。 (prchild)==NULL) //如果是葉子結(jié)點 { printf(%d,pw)。 printf(the hops of the node is: %d\n,n)。 WPL=WPL+n*(pw)。 //計算權(quán)值 } travel(plchild,n+1)。 travel(prchild,n+1)。 } } struct ptree *hafm(int n, int w[m]) { struct pforest *p1,*p2,*f。 struct ptree *ti,*t,*t1,*t2。 int i。 f=(struct pfores *)malloc(sizeof(struct pforest))。 flink=NULL。 for(i=1。i=n。i++) //產(chǎn)生 n棵只有根結(jié)點的二叉樹 { ti=(struct ptree*)malloc(sizeof(struct ptree))。 //開辟新的結(jié)點空間 tiw=w[i]。 //給結(jié)點賦權(quán)值 tilchild=NULL。 tirchild=NULL。 f=inforest (f, ti)。 } while(((flink)link)!=NULL)//至少有二棵二叉樹 { p1=flink。 p2=p1link。 flink=p2link。 //取出前兩棵樹 flink=p2link。 //取出前兩棵樹 t1=p1root。 t2=p2root。 free(p1)。 //釋放 p1 free(p2)。 //釋放 p2 t=(struct ptree *)malloc(sizeof(struct ptree))。 //開辟新的結(jié)點空間 tw=t1w+t2w。 //權(quán)相加 tlchild=t1。 trchild=t2。 //產(chǎn)生新二叉樹 f=inforest(f,t)。 } p1=flink。 t=p1root。 free(f)。 return(t)。 //返回 t } struct pforest *inforest(struct pforest *f, sturct ptree *t) { struct pforest *p, *q, *r。 struct ptree *ti。 r=(struct pforest *)malloc(sizeof(struct pforest))。 //開辟新的結(jié)點空間 rroot=t。 q=f。 p=flink。 while (p!=NULL) //尋找插入位置 { ti=proot。 if (twtiw) //如果 t的權(quán)值大于 ti的權(quán)值 { q=p。 p=plink。 //p向后尋找 } else p=NULL。 //強迫退出循環(huán) } rlink=qlink。 qlink=r。 //r接在 q的后面 return(f)。 //返回 f } 3． 哈夫曼編碼 哈夫曼樹的應用很廣，哈夫曼編碼就是哈夫曼樹在電訊通信中的應用之一。 通訊中常需要將文字轉(zhuǎn)換成二進制字符串電文進行傳送。 文字 電文，稱為 編碼 。 收到電文后要將電文轉(zhuǎn)換成原來的文字， 電文 文字，稱為 譯碼 。 在電報通信中，電文是以二進制的 0， 1序列傳送的。在發(fā)送端需要將電文中的字符轉(zhuǎn)換成 0， 1序列（編碼）發(fā)送，在接收端又需要把接收到的 0， 1序列還原成相應的字符序列（譯碼）。 最簡單的二進制編碼方式是等長編碼。假定需傳送的電文是CDABB， 在電文中僅使用 A， B， C， D 4種字符，則只需用兩個字符串便可分辨?？梢来螌ζ渚幋a為： 00， 01， 10， 11。上述需發(fā)送的的電文是 “ 1011000101” 。譯碼員可按兩位一組進行譯碼，恢復原來的電文。 例如：需將文字“ ABACCDA”轉(zhuǎn)換成電文。文之中 有四種字符，用 2位二進制便可分辨。 A B C D 00 01 10 11 編碼方案 1： 則上述文字的電文為： 00010010101100 共 14位。 譯碼時，只需每 2位一譯即可。 特點：等長等頻率編碼，譯碼容易，但電文不一定最短。 A B C D 0 00 1 01 編碼方案 2： 采用不等長編碼，讓出現(xiàn)次數(shù)多的字符用短碼。 則上述文字的電文為： 000011010 共 9位。 但無法譯碼，它既可譯為 BBCCACA， 也可譯為 AAAACCDA等。 A B C D 0 110 10 111 編碼方案 3： 采用不等長編碼，讓出現(xiàn)次數(shù)多的字符用短碼，且任一編碼不能是另一編碼的前綴。 則上述文字的電文為： 0110010101110 共 13位。 設(shè)有 n種字符，每種字符出現(xiàn)的次數(shù)為 Wi , 其編碼長度為 Li (i=1,2,．．． n)， 則整個電文總長度為 ∑ Wi Li ， 要得到最短的電文，即使得 ∑ Wi Li最小。 也就是以字符出現(xiàn)的次數(shù)為權(quán)值，構(gòu)造一棵 Huffman樹，并規(guī)定左分支編碼位 0，右分支編碼為1，則字符的編碼就是從根到該字符所在的葉結(jié)點的路徑上的分支編號序列。 用構(gòu)造 Huffman樹編出來的碼，稱為 Huffman編碼。 為了獲得傳送電文的最短長度，可將字符出現(xiàn)的次數(shù)（頻率）作為權(quán)值賦予該結(jié)點，構(gòu)造一棵 WPL最小的哈夫曼樹，由此得到的二進制前綴編碼就是最優(yōu)前綴編碼，也稱哈夫曼編碼?？梢则炞C，用這樣的編碼傳送電文可使總長最短。 ABC D000 11101 01 1 0 1 1 1 96 64 50001 110ET1 41DA R2 11 2圖 622 哈夫曼編碼 圖 623 最優(yōu)編碼示例 例如，設(shè)一文本的字符序列是： DATA TRERTER ARE AREA ART，此 文本的字符集為 {A， D， T， R， E}， 各字符出現(xiàn)的次數(shù)為 {6， 1，4， 6， 4}。以此為權(quán)值，構(gòu)造一棵最優(yōu)二叉樹（哈夫曼樹），如圖 623所示。 約定從各非終端結(jié)點發(fā)出的左分支表示 0，右分支表示 1。于是，由根結(jié)點到葉結(jié)點的路徑上所有 0和 1組成的序列，就是該葉結(jié)點所表字符的哈夫曼編碼。如下所示： 字符 A D T R E 編碼 10 010 011 11 00 由此可見，根據(jù)權(quán)值構(gòu)造哈夫曼樹得出的哈夫曼編碼，使字符出現(xiàn)次數(shù)（頻率）與碼長呈反比關(guān)系，如此得到的電文總碼長最短；同時，又避免了每一個字符編碼是另一個字符編碼的前綴，保證了譯碼的唯一性。 本章主要介紹了樹和二叉樹兩種數(shù)據(jù)結(jié)構(gòu)的定義以及它們的存儲結(jié)構(gòu)和運算定義。 樹是以分支關(guān)系定義的層次結(jié)構(gòu)，結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著“ 一對多 ” 的關(guān)系。樹中除根結(jié)點沒有前驅(qū)外，其它每個結(jié)點只有一個前驅(qū)；所有結(jié)點都有零個或多個后繼。因此樹型結(jié)構(gòu)為自然界和計算機應用中出現(xiàn)的具有層次關(guān)系或分支關(guān)系的數(shù)據(jù)，提供了一種自然的表示方法。 如可用樹型結(jié)構(gòu)描述人類社會的族譜和各種社會組織機構(gòu)等。 在計算機學科和應用領(lǐng)域中，樹也得到廣泛應用。例如在編譯程序中，可用樹來表示源程序的語法結(jié)構(gòu)等。樹還是一種典型的遞歸結(jié)構(gòu)。 二叉樹是另一種樹型結(jié)構(gòu)，是度為 2的有序樹。本章重點討論了二叉樹。二叉樹中每個結(jié)點至多有兩個孩子，它有明確的左、右之分。 一棵深度為 h的二叉樹，最少含有 h個結(jié)點，最多含有 2h1個結(jié)點一棵具有 n個結(jié)點的二叉樹，其最小深度為 ?log2n」 +1。 本章小結(jié) 二叉樹具有順序和鏈式兩種存儲結(jié)構(gòu)。對于完全二叉樹通常采用順序存儲結(jié)構(gòu)，對于普通二叉樹通常采用鏈式存儲結(jié)構(gòu)。 樹和二叉樹的遍歷算法是實現(xiàn)各種操作的基礎(chǔ)。是把非線性結(jié)構(gòu)變成線性結(jié)構(gòu)的一種排列方式。對這種非線性結(jié)構(gòu)的遍歷需要選擇合適的搜索路徑，以確保在這條路徑上可以訪問到結(jié)構(gòu)中的所有數(shù)據(jù)元素。它包括先序、中序、后序三種不同的遍歷次序（樹沒有中序遍歷）。要求讀者能熟練掌握二叉樹的前序，中序，后序遍歷的遞歸算法，以及樹和二叉樹之間，森林和樹之間轉(zhuǎn)換的具體方法，熟悉線索二叉樹的定義及其線索化算法。 作為應用，最后介紹了最優(yōu)二叉樹和最優(yōu)前綴編碼的構(gòu)造方法。最優(yōu)二叉樹是一種 “ 帶權(quán)路徑長度 WPL”最短的二叉樹，最優(yōu)前綴編碼（哈夫曼編碼）是最優(yōu)二叉樹的一種應用。 第 6章 樹和二叉樹 樹的定義和