樹 - 哈夫曼樹及其應用 - 最優二叉樹（二）

　　構造最優二叉樹

　　哈夫曼算法

　　哈夫曼首先給出了對於給定的葉子數目及其權值構造最優二叉樹的方法故稱其為哈夫曼算法其基本思想是

　　()根據給定的n個權值w l w …w n 構成n棵二叉樹的森林F={T T …T n }其中每棵二叉樹T i 中都

　　只有一個權值為w i 的根結點其左右子樹均空

　　()在森林F中選出兩棵根結點權值最小的樹(當這樣的樹不止兩棵樹時可以從中任選兩棵)將這兩棵樹合並成一棵新樹為

　　了保證新樹仍是二叉樹需要增加一個新結點作為新樹的根並將所選的兩棵樹的根分別作為新根的左右孩子(誰左誰右無關緊要

　　)將這兩個孩子的權值之和作為新樹根的權值

　　()對新的森林F重復()直到森林F中只剩下一棵樹為止這棵樹便是哈夫曼樹

　　用哈夫曼算法構造哈夫曼樹的過程見【 動畫演示 】

　　注意

　　① 初始森林中的n棵二叉樹每棵樹有一個孤立的結點它們既是根又是葉子

　　② n個葉子的哈夫曼樹要經過n次合並產生n個新結點最終求得的哈夫曼樹中共有n個結點

　　③ 哈夫曼樹是嚴格的二叉樹沒有度數為的分支結點

　　哈夫曼樹的存儲結構及哈夫曼算法的實現

　　() 哈夫曼樹的存儲結構

　　用一個大小為n的向量來存儲哈夫曼樹中的結點其存儲結構為

　　#define n //葉子數目

　　#define m *n//樹中結點總數

　　typedef struct { //結點類型

　　float weight; //權值不妨設權值均大於零

　　int lchildrchildparent; //左右孩子及雙親指針

　　}HTNode;

　　typedef HTNode HuffmanTree[m]; //HuffmanTree是向量類型

　　注意

　　因為C語言數組的下界為故用表示空指針樹中某結點的lchildrchild和parent不等於時它們分別是該結點的左

　　右孩子和雙親結點在向量中的下標

　　這裡設置parent域有兩個作用其一是使查找某結點的雙親變得簡單;其二是可通過判定parent的值是否為來區分根與非根結

　　點

　　()哈夫曼算法的簡要描述

　　在上述存儲結構上實現的哈夫曼算法可大致描述為(設T的類型為HuffmanTree)

　　()初始化

　　將T[m]中n個結點裡的三個指針均置為空(即置為)權值置為

　　()輸人

　　讀人n個葉子的權值存於向量的前n個分量(即T[n])中它們是初始森林中n個孤立的根結點上的權值

　　()合並

　　對森林中的樹共進行n次合並所產生的新結點依次放人向量T的第i個分量中(n≤i≤m)每次合並分兩步

　　①在當前森林T[i]的所有結點中選取權最小和次小的兩個根結點[p]和T[p]作為合並對象這裡≤pp≤i

　　② 將根為T[p]和T[p]的兩棵樹作為左右子樹合並為一棵新的樹新樹的根是新結點T[i]具體操作

　　將T[p]和T[p]的parent置為i

　　將T[i]的lchild和rchild分別置為p和p

　　新結點T[i]的權值置為T[p]和T[p]的權值之和

　　注意

　　合並後T[pl]和T[p]在當前森林中已不再是根因為它們的雙親指針均已指向了T[i]所以下一次合並時不會被選中為合並對象

　　哈夫曼算法模擬演示過程【 參見動畫模擬 】

　　()哈夫曼算法的求精

　　void CreateHuffmanTree(HuffmanTree T)

　　{//構造哈夫曼樹T[m]為其根結點

　　int ipp;

　　InitHuffmanTree(T); //將T初始化

　　InputWeight(T); //輸入葉子權值至T[n]的weight域

　　for(i=n;i

　　SelectMin(T，i-1，&p1，&p2);

　　//在T[0..i-1]中選擇兩個權最小的根結點，其序號分別為p1和p2

　　T[p1].parent=T[p2].parent=i;

　　TIi].1child=p1; //最小權的根結點是新結點的左孩子

　　T[j].rchild=p2; //次小權的根結點是新結點的右孩子

　　T[i].weight=T[p1].weight+T[p2].weight;

　　} // end for

　　}

　　上述算法中調用的三個函數【參見練習】。tW.WinGwIt.COm

　　【例】以7個權值：7，5，1，4，8，10，20為例，執行CreateHuffmanTree求最優二叉樹的過程

From:http://tw.wingwit.com/Article/program/sjjg/201311/23864.html