哈夫曼树的构建过程

构建哈夫曼树的过程~

第一步，1是最小堆，将较小的2放入，此堆变为3
第二步，3和第一步的1、2之和大小相同，任取一个作为最小堆，把其余较小元素并入

例如：1，3，2，4，6，10
第一步：（1，2），3，4，5，10 ---1作为最小堆，2放入
第二步：（（1，2），3），4，5，10
第三步：（（1，2），3），（4，5），10 ------此时4是最小堆，5放入
第四步：（（（1，2），3），（4，5）），10
第五步：（（（（1，2），3），（4，5）），10）

。。作业吧，运行可用，自己再试试。

//huffman_h.h 哈夫曼树的头文件
#include"iostream.h"
#include "stdio.h"
#include "stdlib.h"
#include "string.h"

typedef char ElemType;
typedef struct{
ElemType elem;
unsigned int weight;
unsigned int parent,lchild,rchild,tag;
}HTNode,*HuffmanTree;
typedef char** HuffmanCode;

typedef int Status;
typedef struct weight
{
char elem;
unsigned int m_weight;
}Weight; // 保存符号信息;

void Select(HuffmanTree HT,int n,int &s1,int &s2)
{
int i;
s1=s2=0;
for(i=1;i<=n;i++){
if(HT[i].weight<HT[s2].weight&&HT[i].parent==0&&s2!=0){
if(HT[i].weight<HT[s1].weight) {
s2=s1; s1=i; }
else s2=i;
}
if((s1==0||s2==0)&&HT[i].parent==0){
if(s1==0) s1=i;
else if(s2==0) {
if(HT[i].weight<HT[s1].weight) {
s2=s1; s1=i; }
else s2=i;


} // end of else if
if(s1>s2) {i=s1; s1=s2; s2=i;}
// end of if
// end of for

}

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, Weight* &w, int n) {
// w存放n个字符的权值(均>0)，构造哈夫曼树HT，
// 并求出n个字符的哈夫曼编码HC
//本函数实现选择方式：从左往右选择两个小权值结点，结点信息在前面的为左子树，其后为右子树
//修改选择方式：依序选择两个小权值结点，权值小的为左子树。！！

int i, j, m, s1,s2;
char *cd;
int p;
int cdlen;

if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用
for (i=1; i<=n; i++) { //初始化
HT[i].elem=w[i-1].elem;
HT[i].weight=w[i-1].m_weight;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i<=m; i++) { //初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
printf("
哈夫曼树的构造过程如下所示：
");
printf("HT初态:
结点 weight parent lchild rchild");
for (i=1; i<=m; i++)
printf("
%4d%8d%8d%8d%8d",i,HT[i].weight,
HT[i].parent,HT[i].lchild, HT[i].rchild);
printf(" 按任意键，继续 ...");
getchar();
for (i=n+1; i<=m; i++) { // 建哈夫曼树
// 在HT[1..i-1]中选择parent为0且weight最小的两个结点，
// 其序号分别为s1和s2。
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;
printf("
select: s1=%d s2=%d
", s1, s2);
printf(" 结点 weight parent lchild rchild");
for (j=1; j<=i; j++)
printf("
%4d%8d%8d%8d%8d",j,HT[j].weight,
HT[j].parent,HT[j].lchild, HT[j].rchild);
printf(" 按任意键，继续 ...");
getchar();
}//for

//------无栈非递归遍历哈夫曼树，求哈夫曼编码
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
cd = (char *)malloc((n+1)*sizeof(char)); // 分配求编码的工作空间
p = m; cdlen = 0;
for (i=1; i<=m; ++i) // 遍历哈夫曼树时用作结点状态标志
HT[i].tag = 0;
while (p) {
if (HT[p].tag==0) { // 向左
HT[p].tag = 1;
if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; }
else if (HT[p].rchild == 0) { // 登记叶子结点的字符的编码
HC[p] = (char *)malloc((cdlen+1) * sizeof(char));
cd[cdlen] ='\0'; strcpy(HC[p], cd); // 复制编码(串)
}
} else if (HT[p].tag==1) { // 向右
HT[p].tag = 2;
if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; }
} else { // HT[p].weight==2，退回退到父结点，编码长度减1
HT[p].tag = 0; p = HT[p].parent; --cdlen;
}//else
}//while
} // HuffmanCoding

/*
//--- 从叶子到根逆向求每个字符的哈夫曼编码 ---
cd = (char *)malloc(n*sizeof(char)); // 分配求编码的工作空间
cd[n-1] = '\0'; // 编码结束符。
for (i=1; i<=n; ++i) { // 逐个字符求哈夫曼编码
start = n-1; // 编码结束符位置
for (c=i, f=HT[i].parent; f!=0; c=f, f=HT[f].parent)
// 从叶子到根逆向求编码
if (HT[f].lchild==c) cd[--start] = '0';
else cd[--start] = '1';
HC[i] = (char *)malloc((n-start)*sizeof(char));
// 为第i个字符编码分配空间
strcpy(HC[i], &cd[start]); // 从cd复制编码(串)到HC
}
free(cd); // 释放工作空间
*/



void OutputHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n)
{
int i;
printf("
number---element---weight---huffman code
");
for(i=1;i<=n;i++)
printf(" %d %c %d %s
",i,HT[i].elem,HT[i].weight,HC[i]);
}

//主函数
//huffman.cpp
#include"huffman_h.h"

void main()
{
HuffmanTree HT;
HuffmanCode HC;
Weight *w;
char c; // the symbolizes;
int i,n; // the number of elements;
int wei; // the weight of a element;

printf("请输入构建哈夫曼树的结点数:" );
cin>>n; //cout<<endl;
w=(Weight *)malloc(n*sizeof(Weight));
for(i=0;i<n;i++)
{
//cout<<"请输入第"<<i+1<<"个结点编号及其权值（如a 100）:"<<endl;
printf("请输入结点编号及其权值（如a 100）:" );
scanf("%1s%d",&c,&wei);
w[i].elem=c;
w[i].m_weight=wei;
}

HuffmanCoding(HT,HC,w,n);
OutputHuffmanCode(HT,HC,n);
}

哈夫曼树:
给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
哈夫曼树的构造：
假设给定的权值如下：3,5,7,8,10,15；
首先取集合中最小的两个数：3+5=8，再删除集合中3和5的值，把8放入原集合,
原集合变成:7,8,8,10,15；
8
/ \
3 5
再从7,8,8,10,15中再取2个最小的数构成一个树
15
/ \
8 7
/ \
3 5
再从8,10,15,15中再取2个最小的数构成一个树:
18
/ \
8 10
再从15,15,18中取两个最小数:15,15,构成树:
30
/ \
15 15
/ \
8 7
/ \
3 5
最后把18,30构成树(此时集合中已经没元素了，就形成了哈夫曼树):
48
/ \
30 18
/ \ / \
15 15 8 10
/ \
8 7
/ \
3 5
希望你能看懂！！

---

市南区18513123127： 哈夫曼树的构建过程 - ？
路省荆花： 哈夫曼树: 给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman tree).哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近. 哈夫曼树的构造: 假...

市南区18513123127： 权值序列为:10,16,20,6,30,24,如何构造出一棵哈夫曼树? - ？
路省荆花：[答案] 哈夫曼树构造规则是先从序列中选取两个最小的权值的点来构造树,新的树根的权值是两个左右子节点的权值和,该新的权值然后放回到权值序列中.迭代这个过程直到只有一棵树为止. 所以该哈夫曼树是: 106 / \ 44 62 / \ / \ 20 24 30 32 / \ 16 16 / \ 6 10

市南区18513123127： 请描述哈夫曼算法,并用图描述构造哈夫曼树的过程. - ？
路省荆花： 这个讲的相当清楚.首先介绍什么是哈夫曼树.哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树.所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其...

市南区18513123127： 怎样构造合适的哈夫曼树? - ？
路省荆花： 来自百度百科:哈夫曼树构造方法:假设有n个权值,则构造出的哈夫曼树有n个叶子结点. n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:(1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);(2) 在森...

市南区18513123127： 哈夫曼树怎样构造编码? - ？
路省荆花： 先编造哈夫曼树,哈夫曼树构造规则: 假设有n个权值,则构造出的哈夫曼树有n个叶子结点. n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为: (1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点); (2) ...

市南区18513123127： 哈夫曼树的建立 - ？
路省荆花： 给你个大概的代码,把显示跟调用那里改改#include #include #include#include typedef struct { unsigned int weight; unsigned int parent,lchild,rchild,ch; }HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树 typedef char *HuffmanCode; //动态分配...

市南区18513123127： 赫夫曼树的建立 - ？
路省荆花： 给你一个全功能的代码,关于,hufman tree的,你要哪一段就自己节选:/* Note:Your choice is C IDE */#include ＂stdio.h＂#include ＂stdlib.h＂#define N 20/*叶子最大结点数*/ typedef struct { int weight;/*假设叶子权值为整型*/ int lchild,rchild,...

市南区18513123127： 动态演示哈夫曼树的生成过程？
路省荆花： #include &lt;stdio.h&gt;/ #include &lt;stdlib.h&gt;/*哈夫曼树建立、哈夫曼编码算法的实现*/ #include &lt;string.h&gt; typedef char* HuffmanCode;/*动态分配数组,存储哈夫曼编码*/ typedef struct { unsigned int weight ; /* 用来存放各个结点的权...

市南区18513123127： 怎么构造哈夫曼树？
路省荆花： #include <stdio.h> #include <conio.h> #include <stdio.h> #define M 10 #define MAX 100 typedef struct { int data; int pa,lc,rc; }JD; void huffman(int n,int w[],JD t[]) { int i,j,k,x1,x2,m1,m2; for(i=1;i<(2*n);i++) { t[i].pa=t[i].lc=t[i].rc=0; if(i<=n) t[i].data=w[i-1]; ...

市南区18513123127： 动态演示哈夫曼树的生成过程 - ？
路省荆花： #include <stdio.h>/#include <stdlib.h>/*哈夫曼树建立、哈夫曼编码算法的实现*/#include <string.h> typedef char* HuffmanCode;/*动态分配数组,存储哈夫曼编码*/ typedef struct { unsigned int weight ; /* 用来存放各个结点的权值*/ unsigned int ...