当前位置：首页 > article >正文

树——哈夫曼树的概念及其应用

article 2025/9/12 9:00:12

哈夫曼概念

引入

哈夫曼概念：

引入：

由上述对比，为找到效率最高的判别树，引入了哈夫曼树（最优二叉树）的概念。

基本概念：

特点：

满二叉树不一定是哈夫曼树

哈夫曼树中权越大的叶子离根越近

具有相同带权结点的哈夫曼树不唯一

哈夫曼树的构造算法：

1.哈夫曼算法：

包含n个叶子结点的哈夫曼树中共有2n-1个结点。

哈夫曼树由两两合并得到的，所以n个结点一定合并n-1次，生成n-1个新结点。所以共有n+n-1=2*n-1个结点。

举例：

2.哈夫曼树算法实现：

举例：有n=8，权值为W={7，19，2，6，32，3，21，10}，来构造哈夫曼树。

第一步：

第二步：在parent为0的里面再选择两个较小的，以此类推，每次都这样。

第三步：

第四步：

第五步：

依此类推，直到最后：（只剩下一个parent的值为0时）

实现：

初始化

进行n-1次合并

总体上的代码是这样子的（一部分）：

首先是定义：

//定义 
typedef struct HTNode
{int weight;int parent,lch,rch; 
}HTNode,*HuffmanTree;

其次是建立：

typedef int Status;
void CreateHuffmanTree(HuffmanTree &HT,int n);//建立哈夫曼树 
int Select(HuffmanTree HT,int n,int &s1,int &s2);//找权值最小的两个结点，并返回它们在HT中的序号s1,s2 
int main() 
{HuffmanTree HT;int n;//函数调用 CreateHuffmanTree(HT,n);
} 
//建立哈夫曼树 
void CreateHuffmanTree(HuffmanTree &HT,int n)
{if(n<=1) return;int m=2*n-1;HT=new HTNode[m+1];for(int i=1;i<=m;++i){HT[i].lch=0;HT[i].rch=0;HT[i].parent=0;}for(int i=1;i<=n;i++){cin>>HT[i].weight;}for(int i=n+1;i<=m;i++){int s1,s2;Select(HT,i-1,s1,s2);HT[s1].parent=i;HT[s2].parent=i;HT[i].lch=s1;HT[i].rch=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;} 
}
//找权值最小的两个结点，并返回它们在HT中的序号s1,s2 
int Select(HuffmanTree HT,int n,int &s1,int &s2)
{int a[MAXSIZE];for(int j=1;j<n;j++){int k=0;if(HT[k].parent!=0){a[j]=HT[k].weight;k++;}elsek++;//进行排序，找权值最小的两个结点for(int h=1;h<=n;h++)for(int g=1;g<n-h;g++){if(a[g]>a[g+1]){int t;t=a[g];a[g]=a[g+1];a[g+1]=t; }}//返回它们在HT中的序号 s1=a[1];s2=a[2];}
}

当然这不是完整的代码。