計算機演算法的設計與分析實驗報告
1、描述
在權為wl，w2，…，wn的n個葉子所構成的所有二叉樹中，帶權路徑長度最小(即代價最小)的二叉樹稱為最優二叉樹或哈夫曼樹。
【例】給定4個葉子結點a，b，c和d，分別帶權7，5，2和4。構造如下圖所示的三棵二叉樹(還有許多棵)，它們的帶權路徑長度分別為：
(a)wpl=7*2+5*2+2*2+4*2=36
(b)wpl=7*3+5*3+2*1+4*2=46
(c)wpl=7*1+5*2+2*3+4*3=35
其中(c)樹的wpl最小，可以驗證，它就是哈夫曼樹。
注意： ① 葉子上的權值均相同時，完全二叉樹一定是最優二叉樹，否則完全二叉樹不一定是最優二叉樹。 ② 最優二叉樹中，權越大的葉子離根越近。
③ 最優二叉樹的形態不唯一，wpl最小
2、**
#include ""
#include<>
#include<>
#include<>
#define number 4
typedef struct
htnode, *huffmantree;
//最小數
int _min(huffmantree ht, int i)
//次小數
int _sec_min(huffmantree ht, int i)
//列印赫夫曼樹
void printf_huffmantree(huffmantree ht, int n)
}void huffmancoding(huffmantree ht, int *w, int n)
for(; i
for(i = n; i
printf_huffmantree(ht, n);
}int main()
huffmancoding(ht, weight, number);
return 0;
}3、結果
4、分析
哈夫曼樹的應用很廣，哈夫曼編碼就是哈夫曼樹在電訊通訊中的應用之一。它採用不等長編碼，讓出現次數多的字元用短碼，且任一編碼不能是另一編碼的字首（我們稱之為字首編碼，或非字首碼）。設有n種字元，每種字元出現的次數為wi，其編碼長度為li (i=1,2,．．．n)，則整個電文總長度為∑ wi li ，要得到最短的電文，即使得∑ wi li最小。
也就是以字元出現的次數為權值，構造一棵 huffman樹，並規定左分支編碼位0，右分支編碼為1，則字元的編碼就是從根到該字元所在的葉結點的路徑上的分支編號序列。用構造huffman樹編出來的碼，稱為huffman編碼。
為了獲得傳送電文的最短長度，可將字元出現的次數（頻率）作為權值賦予該結點，構造一棵wpl最小的哈夫曼樹，由此得到的二進位制字首編碼就是最優字首編碼，也稱哈夫曼編碼。可以驗證，用這樣的編碼傳送電文可使總長最短。
二叉樹遍歷技巧
二叉樹先根序 後根序 中根序遍歷的速演算法 解題技巧 經過研究我找出了一種不用畫圖，由先 後 根序遍歷和中根序遍歷迅速確定遍歷結果的辦法。謹以此文獻給智商與我同級而又不得不研究演算法的朋友。抽象思維太差，用例子來說明吧。下面這個是後根遍歷的演算法。例1 已知某二叉樹的先根序遍歷為abcdefg,中根...
二叉樹的遍歷
飛機票訂票系統 二 一四年六月 二叉數的遍歷 1 問題陳述 二叉樹的中序 前序 後序的遞迴 非遞迴遍歷演算法，層次序的非遞迴遍歷演算法的實現，應包含建樹的實現。限1 人完成 二叉樹的前序 後序的遞迴 非遞迴遍歷演算法，層次序的非遞迴遍歷演算法的實現，應包含建樹的實現。先序遍歷二叉樹演算法 若二叉樹為...
二叉樹歷遍
對於例題的後序遍歷的答案是，gdbehfca.解答過程 1 定 釋 樹的遍歷的三種情況，是根據左子樹 右子樹 根這3者的不同訪問次序來定義的。根左右 根先訪問 則為先序遍歷 左根右，則為中序遍歷 左右根，則為後序遍歷。2 已知先序和中序遍歷結果，求樹的結構和後序遍歷結果 先序遍歷結果給我們帶來的資訊...