《數(shù)據(jù)結構（C語言描述）（第2版）》教學課件4-13構造哈夫曼樹的算法

1、2016數(shù)據(jù)結構Data structure講授：劉斌構造哈夫曼樹的算法常州信息職業(yè)技術學院02教學目標123哈夫曼樹結點的結構03哈夫曼樹的描述構造哈夫曼樹的步驟4構造哈夫曼樹具體算法三、鏈表的插入04構造哈夫曼樹的算法1.33哈夫曼樹及哈夫曼編碼3、構造哈夫曼樹的算法1哈夫曼樹結點的結構哈夫曼樹的結點用一個大小為2n-1的向量來存儲，每個結點包含權值域weight、指示左右孩子結點在向量中下標的整型量lchild和rchild、指示雙親結點在向量中下標的整型量parent。lchildweightparentrchild圖4-26 結點結構weightlchildrchildparent0

2、5構造哈夫曼樹的算法1.3122哈夫曼樹的描述#define n 100 /葉子數(shù)目#define m 2*n-1/樹中結點總數(shù)typedef struct /定義結點類型 double weight; /定義權值域 int lchild,rchild,parent; /定義左右孩子及雙親指針HTNode;typedef HTNode HuffmanTreem; /*定義HuffmanTree為新的類型標識符，用該標 符定義的變量是具有HTNode類型的含有m個元素的向量。*/C數(shù)組的下界為0，故用-1表示空指針。樹中某結點的lchild、rchild和parent不等于-1時，它們分別是該結

3、點的左、右孩子和雙親結點在向量中的下標。設置parent域有兩個作用：其一是使查找某結點的雙親變得簡單；其二是可通過判定parent的值是否為-1來區(qū)分根與非根結點。（iii）新結點Ti的權值置為Tp1和Tp2的權值之和。 06構造哈夫曼樹的算法1.33構造哈夫曼樹T的步驟（1）初始化：將T0m-1中2n-1個結點里的三個指針均置為空（即置為-1），權值置為0。（2）輸入：讀入n個葉子的權值存于向量的前n個分量（即T0 n-1）中。它們是初始森林中n個孤立的根結點上的權值。（3）合并：對森林中的樹共進行n-1次合并，所產(chǎn)生的新結點依次放入向量T的第i個分量中（nim-1）。每次合并分兩步：在當

4、前森林T0 i-1的所有結點中，選取權最小和次小的兩個根結點Tp1和Tp2作為合并對象，這里0p1，p2i-1。 將根為Tp1和Tp2的兩棵樹作為左右子樹合并為一棵新的樹，新樹的根是新結點Ti。（iii）新結點Ti的權值置為Tp1和Tp2的權值之和。 06構造哈夫曼樹的算法1.3具體操作:（i）將Tp1和Tp2的parent置為i;（ii）將Ti的lchild和rchild分別置為p1和p2;（iii）新結點Ti的權值置為Tp1和Tp2的權值之和。 合并后Tpl和Tp2在當前森林中已不再是根，因為它們的雙親指針均已指向了Ti，所以下一次合并時不會被選中為合并對象。07構造哈夫曼樹的算法1.3構

5、造哈夫曼樹T具體算法示例：給定5個葉子結點a，b，c， d和e，分別帶權7，6，12，15和1007構造哈夫曼樹的算法1.3void InitHuffmanTree(HuffmanTree T) /初始化 int i; for (i=0; im; i+) Ti.weight=0;Ti.lchild=-1;Ti.rchild=-1;Ti.parent=-1; 構造哈夫曼樹T具體算法初始化函數(shù)weightlchildrchildparent0-1-1-10-1-1-10-1-1-10-1-1-10-1-1-10-1-1-10-1-1-10-1-1-10-1-1-107構造哈夫曼樹的算法1.3構造哈

6、夫曼樹T具體算法void InputWeight(HuffmanTree T)/輸入權值double w;int i;for (i=0; in;i+) printf(n輸入第%d個權值:,i+1); scanf(%lf,&w); Ti.weight=w;輸入權值函數(shù)weightlchildrchildparent7-1-1-16-1-1-112-1-1-115-1-1-110-1-1-10-1-1-10-1-1-10-1-1-10-1-1-108構造哈夫曼樹的算法1.3void SelectMin(HuffmanTree T, int i, int *p1,int *p2)/選擇兩個小的結點d

7、ouble min1=999999;/定義并初始化最小權值double min2=999999;/定義并初始化次小權值int j;for (j=0;j=i;j+) if(Tj.parent=-1)選擇兩個權最小的根結點函數(shù)if(Tj.weightmin1) min2=min1; /改變最小權,次小權及其位置 min1=Tj.weight; /找出最小的權值 *p2=*p1; *p1=j;else if(Tj.weightmin2) min2=Tj.weight;/改變次小權及位置 *p2=j;weightlchildrchildparent7-1-1-16-1-1-112-1-1-115-1-

8、1-110-1-1-10-1-1-10-1-1-10-1-1-10-1-1-109構造哈夫曼樹的算法1.3void CreateHuffmanTree(HuffmanTree T)/構造哈夫曼樹，Tm-1為其根結點int i,p1,p2;InitHuffmanTree(T); /將T初始化InputWeight(T); /輸入葉子權值至weight域for(i=n;im;i+)/共n-1次合并,新結點存于Ti中SelectMin(T,i-1,&p1,&p2); /選建立哈夫曼樹函數(shù)。擇權最小的根結點Tp1.parent=Tp2.parent=i;Ti.lchild=p1; /最小權根結點是新結

9、點左孩子Ti.rchild=p2; /次小權根結點是新結點右孩子Ti.weight=Tp1.weight+Tp2.weight;weightlchildrchildparent7-1-1-16-1-1-112-1-1-115-1-1-110-1-1-10-1-1-10-1-1-10-1-1-10-1-1-1weightlchildrchildparent7-1-156-1-1512-1-1-115-1-1-110-1-1-11310-10-1-1-10-1-1-10-1-1-1weightlchildrchildparent7-1-156-1-1512-1-1615-1-1-110-1-161310-12242-10-1-1-10-1-1-1weightlchildrchildparent7-1-15