从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径,路径上的分支数目称作路径长度。树的路径长度是从树根到每个结点的路径长度之和。结点的带权路径长度为结点到树根之间的路径长度与结点上权的乘机,树的带权路径长度为树中所有叶子节点的带权路径长度之和。
头文件:
/*****************************************************************************************************
*Copyright: Yue Workstation
*
*FileName: HuffmanTree.h
*
*Function: Huffman树的数据结构定义
*
*Author: Abel Lee
*
*CreateOn: 2012-2-19
*
*Log: 2012-2-19 由Abel Lee创建
*****************************************************************************************************/
#ifndef HUFFMAN_TREE_H
#define HUFFMAN_TREE_H
#include "global.h"
#define NUMBER 4
typedef struct
{
int weight;
int parent, lchild, rchild;
}HTNode, *HuffmanTree;
void PrintHuffmanTree(HuffmanTree ht, int n);
#endif
源文件:
/*****************************************************************************************************
*Copyright:Yue Workstation
*
*FileName: HuffmanTree.c
*
*Function: Huffman树的操作
*
*Author:Abel Lee
*
*CreateOn:2012-2-19
*
*Log:2011-5-3 由Abel Lee创建
*****************************************************************************************************/
#include "../inc/HuffmanTree.h"
//最小数
static int _min(HuffmanTree ht, int i)
{
int j=0;
int temp=0;
for(j = 0; j<i; ++j)
{
if (ht[j].parent == 0)
{
temp = j;
break;
}
}
for(j = temp; j<i; ++j)
{
if (ht[j].parent == 0 && ht[j].weight<ht[temp].weight)
{
temp = j;
}
}
return temp;
}
//次小数
static int _sec_min(HuffmanTree ht, int i)
{
int min = _min(ht, i);
int j=0;
int temp=0;
for(j = 0; j<i; ++j)
{
if (ht[j].parent == 0 && j != min)
{
temp = j;
break;
}
}
for(j = temp; j<i; ++j)
{
if (ht[j].parent == 0 && ht[j].weight<ht[temp].weight && j != min)
{
temp = j;
}
}
return temp;
}
//打印赫夫曼树
void PrintHuffmanTree(HuffmanTree ht, int n)
{
int i = 0;
int temp = 0;
int val = 0;
for (i = 0; i < n; ++i)
{
printf("%d:", ht[i].weight);
val = i;
temp = ht[i].parent;
while (temp)
{
if (ht[temp].lchild == val)
{
printf("0");
}
else if (ht[temp].rchild == val)
{
printf("1");
}
else
{
}
val = temp;
temp = ht[temp].parent;
}
printf("\n");
}
}
/****************************************************************************************************
*Function Name: Huffmancoding
*
*Function: 获取霍夫曼编码
*
*Parameter: ht:huffman树
* w:权值
* n:数量
*
*Return Value: 无
*
*Author:Abel Lee
*
*Log:2012-2-19
***************************************************************************************************/
void Huffmancoding(HuffmanTree ht, int *w, int n)
{//w 存放 n 个字符的权值,构造赫夫曼树 ht, 并求出 n 个字符的赫夫曼编码 hc
int m;
int i;
int min=0, sec_min=0;
HuffmanTree p;
if (n<=1) return;
m = 2*n-1;
ht = (HuffmanTree)malloc(m*sizeof(HTNode));
p = ht;
for(i=0; i<n; ++i, ++p, ++w)//给叶子节点赋值,前n个为叶子节点
{
p->weight = *w;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}
for(; i<m; ++i,++p)//给非叶子节点赋值,第n个到(2*n - 1)个为叶子节点
{
p->weight = 0;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}
for(i = n; i<m; ++i)
{
min = _min(ht, i);
sec_min = _sec_min(ht, i);
ht[min].parent = ht[sec_min].parent = i;
ht[i].lchild = min;
ht[i].rchild = sec_min;
ht[i].weight = ht[min].weight + ht[sec_min].weight;
}
PrintHuffmanTree(ht, n);
}
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。