㈠ void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
很簡單了 typedef struct{ /*哈夫曼樹的存儲表示方法*/ float weight; /* 權重，即概率 */ int parent,lchild,rchild; /*每個結點均有父結點，左孩子，右孩子*/ }HTNode,*HuffmanTree; typedef char **HuffmanCode; /*雙重指針存儲哈夫曼編碼*/ /*哈夫曼編碼的演算法*/ void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) HuffmanTree &HT //這是一棵哈夫曼樹，它是一個已經定義的結構體，此處是引用，不能傳值，當然也可以寫作HuffmanTree *HT HuffmanCode &HC //存儲哈夫曼編碼，可以寫作HuffmanCode *HC /*開始構造一棵哈夫曼樹*/ HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); HC=(HuffmanCode)malloc(n*sizeof(char *)); /*存儲所有概率的編碼*/ - 程序實例 #include #include #include #include #define NULL 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define MAX_NUM 10000 #define MAX 60 typedef int Status; typedef char **HuffmanCode; typedef struct{ unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree; typedef struct{ HuffmanTree HT; char *c; int longth; HuffmanCode HC; }Huffman; void Select(HuffmanTree HT,int end,int *s1,int *s2) { int i; int min1=MAX_NUM; int min2; for (i=1;i<=end;i++) { if (HT[i].parent==0&&HT[i].weightHT[i].weight) { *s2=i; min2=HT[i].weight; } } } Huffman HuffmanCoding(Huffman Hfm) { /*---------------------------------*/ int i,n,m,s1,s2,start; int c,f; char *cd; n=Hfm.longth; if(n<=1) return Hfm; m=2*n-1; for(i=n+1;i<=m;++i) { Select(Hfm.HT,i-1,&s1,&s2); Hfm.HT[s1].parent=i; Hfm.HT[s2].parent=i; Hfm.HT[i].lchild=s1; Hfm.HT[i].rchild=s2; Hfm.HT[i].weight=Hfm.HT[s1].weight+Hfm.HT[s2].weight; } /*--
㈡ 哈夫曼樹HT存儲結構的初態和末態怎麼寫
定義哈夫曼樹與編碼的存儲結構與數據類型
typedef struct
{
char data;//節點值
int weight; //權重
int parent; //雙親節點
int lchild; //左孩子節點
int rchild; //右孩子節點
} HTNode;
typedef struct
{
char cd[N]; //存放哈夫曼碼
int start;
} HCode;
void CreateHT(HTNode ht[],int n) //創建哈夫曼樹
void CreateHCode(HTNode ht[],HCode hcd[],int n) //根據哈夫曼樹計算每個元素的哈夫曼編碼
void DispHCode(HTNode ht[],HCode hcd[],int n) //輸出每個元素的哈夫曼編碼
㈢ 哈夫曼樹
這是我們的作業題，自己寫 的……（可能輸入的格式跟你要的不一致，自己改一下）
如果有什麼不懂的就問我，我可以把其中所有相關的文件發給你 ^^
註：1、 初始化創建哈夫曼樹有三種選擇，其中選擇編譯課本測試數據時和編譯源文件是，調用的輸入文件分別是：test.txt和input.txt；字母的哈夫曼編碼都保存在文件：hmfTree.txt；
2、 用戶自定義模式下，需要編碼的文件內容保存在ToBeTran.txt中；課本測試數據和源文件代碼分別保存在course.txt和sorse.txt中，在（1）中選擇不同的選項，則在編碼時調用相應的文件進行編碼，編碼結果保存在文件CodeFile.txt中。
3、 文件解碼時，調用文件CodeFile.txt進行解碼，得到的結果保存在文件TextFile.txt中。
4、 列印代碼文件：調用CodeFile.txt，結果顯示在終端並保存在文件CodePrin.txt中。
5、 列印哈夫曼樹：用凹入表形式把哈夫曼樹顯示在終端，同時將它保存在文件TreePrint..txt中。
#include <stdio.h>
#include<malloc.h>
#include <string.h>
#include<fstream>
#include<iostream>
using namespace std;
typedef struct {
unsigned int weight;
char ch1;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
typedef struct {
char ch;
char code[7];
}codenode,*code;
void select(HuffmanTree HT,int n,int & s1,int &s2){ //從哈夫曼樹中選擇出最小的兩個節點
for(int i=1;i<=n;i++)
if(!HT[i].parent){
s1=i; break;
}
for(i++;i<=n;i++)
if(!HT[i].parent){
s2=i; break;
}
if(HT[s1].weight-HT[s2].weight){
int temp; temp=s1; s1=s2; s2=temp;
}
for(i=1;i<=n;i++) //對數組進行遍歷，尋找最小的兩個節點
if(!HT[i].parent){
if(HT[i].weight<HT[s1].weight){
s2=s1; s1=i;
}
else if(HT[i].weight<HT[s2].weight&&i!=s1)
s2=i;
}
}
void prin(){ //終端輸出選擇菜單
cout<<"----------------------------------------------------\n\n"
<<" ∣ I---創建哈夫曼樹 ∣\n"
<<" ∣ ∣\n"
<<" ∣ E---文件編碼 ∣\n"
<<" ∣ ∣\n"
<<" ∣ D---文件解碼 ∣\n"
<<" ∣ ∣\n"
<<" ∣ P---列印代碼文件 ∣\n"
<<" ∣ ∣\n"
<<" ∣ T---印哈夫曼樹 ∣\n"
<<" ∣ ∣\n"
<<" ∣ O---哈夫曼樹的存儲結構 ∣\n"
<<" ∣ ∣\n"
<<" ∣ Q---退出 ∣\n"
<<"\n-----------------------------------------------------\n\n";
printf("選擇菜單功能選項：");
}
void output (HuffmanTree th,int n){ //輸出哈夫曼樹的存儲結構
int i=0;
cout<<"序號"<<" "<<"字元"<<" "<<"雙親"<<" "<<"左孩子"<<" "<<"右孩子"<<" "<<"權值"<<endl;
for(;i<2*n-1;i++){
th++;
cout<<i<<" "<<th->ch1<<" "<<th->parent<<" "<<th->lchild<<" "<<th->rchild<<" "<<th->weight <<endl;
}
}
void initial(HuffmanTree &HT,HuffmanCode &HC,int w[],int &n,char ch[],int &k){ //創建哈夫曼樹
cout<<"----------------------------------------------------\n\n"
<<" ∣ 1---自定義 ∣\n"
<<" ∣ ∣\n"
<<" ∣ 2---編碼課本測試數據 ∣\n"
<<" ∣ ∣\n"
<<" ∣ 3---編碼源程序 ∣\n"
<<"\n-----------------------------------------------------\n\n";
printf("選擇菜單功能選項：");
scanf("%d",&k);
if(k==1){
printf("輸入需要編碼的字元總數: ");
scanf("%d",&n);
printf("\n輸入需要編碼字元的權值:\n");
for(int d=0;d<n;d++) {
scanf("%d",&w[d]);
}
printf("\n輸入需要編碼的字元串: ");
scanf("%s",ch);
}
else if(k==2){
ifstream fin2 ("test.txt");
fin2>>n;
for(int d=0;d<n;d++)
fin2>>w[d];
fin2>>ch;
fin2.close();
}
else if(k==3){
ifstream fin1 ("input.txt");
fin1>>n;
for(int d=0;d<n;d++)
fin1>>w[d];
fin1>>ch;
fin1.close();
}
if(n<=1)
return;
int s1,s2,i,num=2*n-1;
HuffmanTree p;
HT=(HuffmanTree)malloc((num+1)*sizeof(HTNode));
for(p=HT+1,i=1;i<=n;i++,p++){
p->weight=w[i-1]; p->lchild=0; p->parent=0; p->rchild=0; p->ch1 =ch[i-1];
}
for(;i<=num;p++,i++){
p->weight=0; p->lchild=0; p->parent=0; p->rchild=0; p->ch1 ='$';
}
for(i=n+1;i<=num;i++){
select(HT,i-1,s1,s2);
HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1;
HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight;
}
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
char * temp=(char *)malloc(n*sizeof(char));
temp[n-1]='\0';
for(i=1;i<=n;i++){
int start=n-1;
for(int f=HT[i].parent,h=i;f;h=f,f=HT[f].parent)
if(HT[f].lchild==h)
temp[--start]='0';
else
temp[--start]='1';
HC[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(HC[i],&temp[start]);
}
ofstream fout ("hfmTree.txt");
fout<<ch<<endl;
for(int j=1;j<=n;j++)
fout<<HC[j]<<endl;
fout.close();
free(temp);
}
void encoding(int n,int select){ //編碼：對文件TobeTran.txt進行解碼
char a[100],b[100][20];
ifstream fin ("hfmTree.txt");
fin>>a;
for(int j=0;j<n;j++) fin>>b[j];
fin.close();
ifstream fin1 ("course.txt");
ifstream fin2 ("sorse.txt");
ifstream fin3 ("ToBeTran.txt");
char s[1000];
if(select==3)
fin2>>s;
else if(select==2)
fin1>>s;
else fin3>>s;
ofstream fout ("CodeFile.txt");
while(s[0]!='\0'){
for(int i=0;s[i]!='\n'&&s[i]!='\0'&&i<30;i++ ){
for(int g=0;a[g]!=s[i];g++) ;
fout<<b[g];
}
fout<<'\n';
if(select==3)
fin2>>s;
else if(select==2)
fin1>>s;
else fin3>>s;
}
fin3.close();
fin2.close();
fin1.close();
fout.close();
}
void decoding(HuffmanTree ht,int n){ //解碼：對CodeFile.txt文件進行解碼
ifstream fin ("CodeFile.txt");
ofstream fout ("TextFile.txt");
char s[500];
fin>>s;
HuffmanTree head=ht+2*n-1;
int i=0;
while(s[0]!='\0'){
while(s[i]!='\0'){
if(s[i]=='1') head=ht+head->rchild;
else if(s[i]=='0') head=ht+head->lchild;
if((head->lchild)==0&&(head->rchild) ==0) {
fout<<(head->ch1);
head=ht+2*n-1;
}
i++;
}
fout<<' ' ;
i=0;
fin>>s;
}
fin.close();
fout.close();
}
void Print(){ //列印代碼文件，顯示在終端，每行50個代碼
ifstream fin ("CodeFile.txt");
char s[2000];
int j=0;
int i=1;
fin>>s;
ofstream fout ("CodePrin.txt");
while(s[0]!='\0'){
for(;s[j]!='\0';j++){
printf("%c",s[j]);
fout<<s[j];
if(i%50==0){
fout<<endl;
printf("\n");
}
i++;
}
j=0;
fin>>s;
}
fin.close();
printf("\n");
fout.close();
}
void printTree( HuffmanTree node,HuffmanTree node1, int level ) { //列印哈夫曼樹形（在參數的傳遞上，是文科給自己提出的意見才很好的解決了之後的操作難題^^）
if( node == NULL ) return;
if( node1->rchild!=0) {
printTree( node,node+node1->rchild, level + 1 );
}
fstream fout ;
fout.open ("TreePrint.txt",ios::in | ios::out|ios::ate);//這個挺有用的：在文件末尾加入內容
for( int i = 0; i < level; i++ ) {
fout<<"|……";
printf( "……");
}
fout<<node1->weight<<endl;
printf( "%d\n", node1->weight );
if( node1->lchild!=0 ) {
printTree( node,node+node1->lchild, level + 1 );
}
fout.close();
}
void main(){
int select;
int n;
char ch[100];
int w[100];
HuffmanTree HT=NULL;
HuffmanCode hc=NULL;
prin();
char c='I';
scanf("%c",&c);
while(c!='Q'){
switch(c){
case 'I':
initial(HT,hc,w,n,ch,select);
prin();
break;
case 'E':
encoding(n,select);
prin();
break;
case 'D':
decoding(HT,n);
prin();
break;
case 'P':
Print();
prin();
break;
case 'T':
printTree(HT,HT+2*n-1,1);
prin();
break;
case 'O':
output(HT,n);
prin();
break;
}
scanf("%c",&c);
}
}
註：
input.txt文件中保存一下數據：
88
56
26
89
45
62
78
61
13
20
29
89
46
51
25
86
123
20
10
9
57
6
1
57
62
2
37
61
15
19
89
91
2
8
19
49
67
18
19
64
35
67
61
61
84
20
30
50
84
19
28
84
67
31
67
29
20
10
56
56
12
23
56
23
45
85
16
29
94
68
35
97
58
21
29
3
94
58
16
21
64
29
84
64
59
19
48
37
186
!,./;':[]\1234567890-=+)(*&%$#<>"|{}
㈣ Huffman編碼，存儲結構的終結狀態是什麼意思怎麼來的
哈夫曼樹 在一般的數據結構的書中，樹的那章後面，著者一般都會介紹一下哈夫曼(HUFFMAN)樹和哈夫曼編碼。哈夫曼編碼是哈夫曼樹的一個應用。哈夫曼編碼應用廣泛，如JPEG中就應用了哈夫曼編碼。
㈤ 簡述哈夫曼樹的性質。
哈 夫 曼 樹
2.9 二叉樹的應用
2.9.1 哈夫曼樹及應用
哈夫曼樹又稱最優樹（二叉樹），是一類帶權路徑最短的樹。構造這種樹的演算法最早是由哈夫曼(Huffman)1952年提出，這種樹在信息檢索中很有用。
結點之間的路徑長度：從一個結點到另一個結點之間的分支數目。
樹的路徑長度：從樹的根到樹中每一個結點的路徑長度之和。
結點的帶權路徑長度：從該結點到樹根之間的路徑長度與結點上權的乘積。
樹的帶權路徑長度：樹中所有葉子結點的帶權路徑長度之和，記作：
WPL為最小的二叉樹就稱作最優二叉樹或哈夫曼樹。
完全二叉樹不一定是最優二叉樹。
哈夫曼樹的構造：
（1）根據給定的n個權值{w1,w2,...,wn}構造n棵二叉樹的集合F={T1,T2,...,Tn}，其中Ti中只有一個權值為wi的根結點，左右子樹為空；
（2）在F中選取兩棵根結點的權值為最小的數作為左、右子樹以構造一棵新的二叉樹，且置新的二叉樹的根結點的權值為左、右子樹上根結點的權值之和。
（3）將新的二叉樹加入到F中，刪除原兩棵根結點權值最小的樹；
（4）重復（2）和（3）直到F中只含一棵樹為止，這棵樹就是哈夫曼樹。
例1：
例2：
結點的存儲結構:
構造哈夫曼樹的演算法說明：
#define n /* 葉子總數 */
#define m 2*n-1 /* 結點總數 */
證：由性質3，葉子結點數 n0=n2+1，故哈夫曼樹結點總數為 n0+n2=n0+(n0-1)=2*n0-1
例3 在解某些判定問題時，利用哈夫曼樹獲得最佳判定演算法。
（a)
WPL=0.05*1+0.15*2+0.4*3+0.3*4+0.1*4=3.15
（b)(c)
WPL=0.4*1+0.3*2+0.15*3+0.05*4+0.1*4=2.05 WPL=0.05*3+0.15*3+0.4*2+0.3*2+0.1*2=2.2
哈夫曼編碼
從哈夫曼樹根結點開始，對左子樹分配代碼「0」，右子樹分配代碼「1」，一直到達葉子結點為止，然後將從樹根沿每條路徑到達葉子結點的代碼排列起來，便得到了哈夫曼編碼。
例，對電文 EMCAD 編碼。若等長編碼，則
EMCAD => 000001010011100 共15位
設各字母的使用頻度為 {E,M,C,A,D}={1,2,3,3,4}。用頻度為權值生成哈夫曼樹，並在葉子上標注對應的字母，樹枝分配代碼「0」或「1」:
各字母的編碼即為哈夫曼編碼： EMCAD => 000001011011 共12位
2.9.2 二叉排序樹
二叉排序樹是一種特殊結構的二叉樹，它作為一種表的組織手段，通常被稱為樹表。可以作為一種排序和檢索的手段。
定義 二叉排序樹或是空樹，或是具有下述性質的二叉樹：其左子樹上所有結點的數據值均小於根結點的數據值；右子樹上所有結點的數據值均大於或等於根結點的數據值。左子樹和右子樹又各是一棵二叉排序樹。
對二叉排序樹，若按中序遍歷就可以得到由小到大的有序序列。如上圖，中序遍歷得：
{2，3，4，8，9，9，10，13，15，18}
二叉排序樹的生成
對任意一組數據元素序列{R1,R2,...,Rn}，要生成一棵二叉排序樹的過程為：
（1）令R1為二叉樹的根；
（2）若R2<R1，令R2為R1左子樹的根結點，否則R2為R1右子樹的根結點；
（3）對R3,...,Rn結點的插入方法同上。
例，數據元素序列{10，18，3，8，12，2，7，3}，其生成二叉排序樹的過程如下：
二叉排序樹中結點的刪除
要求刪除一個結點後的二叉樹仍是一棵二叉排序樹。演算法思想，分以下幾種情況考慮：
（1）被刪除的結點是葉子結點，則只需修改其雙親結點的指針既可；
（2）被刪除結點p只有左子樹pL或右子樹pR，此時只要使左子樹pL或右子樹pR成為p雙親結點q的左子樹或右子樹即可。
（3）若被刪除結點p的左、右子樹均非空，有兩種做法：
*
令pL直接鏈接到q的左（或右）孩子鏈域上，pR鏈接到p結點中序前趨結點s上（s是pL最右下的結點）；
*
以p結點的直接中序前趨或後繼替代p所指結點，然後再從原二叉排序樹中刪去該直接前趨或後繼。
㈥ 大神們！！ 幫我把哈夫曼樹的代碼 添加以下注釋吧！！！！ 先謝啦！！！ 急。。。
#include<iostream>
using namespace std;
struct htnode //哈夫曼樹結點結構定義
{
char ch; //結點值
int weight; //結點權值
int parent; //父結點下標
int lchild,rchild; //左、右孩子結點下標
};
class huffmantree //哈夫曼樹類定義
{
public:
void code(char str1[],int w[],int n); //編碼
void uncode(char str1[],char str2[],int n); //解碼
private:
htnode ht[3000]; //用數組存儲哈夫曼樹
void creathuffmantree(char str1[],int w[],int n); // 創建哈夫曼樹
void select(int pos,int &r1,int &r2);
};
//在數組ht中從0到pos位置，查找未加入哈夫曼樹的權值最小的兩個數的位置r1,r2
//r1為權值最小的位置，r2為權值第二小的位置
void huffmantree::select(int pos,int &r1,int &r2)
{
r1=r2=0; //初始化為0位置
for(int i=1;i<=pos;i++)
{
if(ht[i].parent!=0) //父結點不等於0，表示已加入哈夫曼樹
continue; //繼續向前查找
if(r1==0) //把r1設置為1
r1=i;
else if(r2==0) //把r2設置為2
r2=i;
//從i等於3開始比較。我認為這里程序有問題，無法得到權最小的兩位置，你自己再改改
else if(ht[i].weight<ht[r1].weight) //如小於r1的權則設置r1為i
r1=i;
else if(ht[i].weight<ht[r2].weight) //如大於r1的權，再和r2的權比較
r2=i;
}
}
// 創建哈夫曼樹，str1[]為結點值數組，w[]為權值數組，共n個結點
void huffmantree::creathuffmantree(char str1[],int w[],int n)
{
int pos;
//把結點值和權值復制到數組ht
for(pos=1;pos<=n;pos++) //注意沒有使用ht數組位置為0的空間
{
ht[pos].weight=w[pos-1]; //結點權值
ht[pos].ch=str1[pos-1]; //結點值
ht[pos].parent=ht[pos].lchild=ht[pos].rchild=0; //父結點為0表示未加入哈夫曼樹，左右孩子都為0表示葉子結點
}
//這是構造哈夫曼樹的過程，即設置數組ht的其他結點
for(pos=n+1;pos<=2*n-1;pos++) //注意用n個數值構造的哈夫曼樹有2*n-1個結點
{
int r1,r2;
select(pos-1,r1,r2);
ht[r1].parent=ht[r2].parent=pos; //把r1，r2結點加入哈夫曼樹，並設置他們的父結點位置為pos
ht[pos].lchild=r1; //設置pos結點的左孩子為r1
ht[pos].rchild=r2; //設置pos結點的右孩子為r2
ht[pos].weight=ht[r1].weight+ht[r2].weight; //設置pos結點的權值為左右孩子權值的和
ht[pos].parent=0; //其父結點為0
}
}
//求哈夫曼編碼
void huffmantree::code(char str1[],int w[],int n)
{
creathuffmantree(str1,w,n); //建立哈夫曼樹
int start,c,i,f,j;
char *cd;
cd=new char[n]; //用於保存哈夫曼編碼
cd[n-1]='\0'; //設置字元串結束符
for(i=1;i<=n;i++) //分別輸出n個結點的哈夫曼編碼
{
start=n-1; //注意從cd數組的末尾向前加入編碼
for(c=i,f=ht[i].parent;f!=0;c=f,f=ht[c].parent) //從葉子結點往上走到根結點為止
{
//左0，右1
if(ht[f].lchild==c)
cd[--start]='0';
else
cd[--start]='1';
}
cout<<"結點"<<str1[i-1]<<"的編碼為："<<endl;
for(j=start;j<n;j++) //輸出所有葉子結點
cout<<cd[j];
cout<<endl;
}
delete []cd; //撤銷
}
//翻譯哈夫曼編碼,str1[]為結點值,str2[]為哈夫曼編碼，共n個結點
//輸出哈夫曼編碼為str2的結點值
void huffmantree::uncode(char str1[],char str2[],int n)
{
int i,f;
char c;
for(i=0;i<strlen(str2);) //從根結點往下走到葉子結點
{
//根結點在數組ht最後一個位置
//從上往下也是左0右1
for(f=2*n-1;ht[f].lchild!=0&&ht[f].rchild!=0;)
{
c=str2[i];
if(c=='1') //等於1往右走
{
f=ht[f].rchild;
i++;
}
else //等於0往左走
{
f=ht[f].lchild;
i++;
}
}
cout<<ht[f].ch; //輸出找到的葉子結點
}
cout<<endl;
}
//這個不用注釋了吧
int main()
{
char str[27],str2[3000],c;
char ch[]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
int cd[27],s,len,i,w[27];
sb1:
cout<<"請輸入要編碼的字元串"<<endl;
cin>>str;
huffmantree obj;
s=0;
memset(cd,0,sizeof(cd));
len=strlen(str);
for(i=0;i<len;i++)
{
cd[str[i]-'a']++;
}
for(i=0;i<26;i++)
{
if(cd[i])
{
str[s]=ch[i];
w[s]=cd[i];
s++;
}
}
cout<<"各節點編碼如下："<<endl;
obj.code(str,w,s);
sb2:
cout<<"請輸入要解碼的01串"<<endl;
cin>>str2;
cout<<"解碼結果如下："<<endl;
obj.uncode(str,str2,s);
cout<<"是否繼續解碼?(Y/N)"<<endl;
getchar();
c=getchar();
if(c=='Y')
goto sb2;
cout<<"是否繼續編碼?(Y/N)"<<endl;
getchar();
c=getchar();
if(c=='Y')
goto sb1;
return 0;
}
㈦ 哈夫曼樹的構造是什麼
哈夫曼樹構造：結構化的Huffman演算法生成的Huffman樹子樹都是有序的，所以一般生成Huffman樹時都為節點排序，即使這樣結果也不唯一。
哈夫曼靜態編碼：它對需要編碼的數據進行兩遍掃描：第一遍統計原數據中各字元出現的頻率，利用得到的頻率值創建哈夫曼樹，並必須把樹的信息保存起來，即把字元0-255(2^8=256)的頻率值以2-4BYTES的長度順序存儲起來，以便解壓時創建同樣的哈夫曼樹進行解壓；第二遍則根據第一遍掃描得到的哈夫曼樹進行編碼，並把編碼後得到的碼字存儲起來。
歷史
1951年，哈夫曼在麻省理工學院（MIT）攻讀博士學位，他和修讀資訊理論課程的同學得選擇是完成學期報告還是期末考試。
導師羅伯特·法諾（Robert Fano）出的學期報告題目是：查找最有效的二進制編碼。由於無法證明哪個已有編碼是最有效的，哈夫曼放棄對已有編碼的研究，轉向新的探索，最終發現了基於有序頻率二叉樹編碼的想法，並很快證明了這個方法是最有效的。
哈夫曼使用自底向上的方法構建二叉樹，避免了次優演算法香農-范諾編碼（Shannon–Fano coding）的最大弊端──自頂向下構建樹。
1952年，於論文《一種構建極小多餘編碼的方法》（A Method for the Construction of Minimum-Rendancy Codes）中發表了這個編碼方法。