使用C语言详解霍夫曼树数据结构


1、基本概念


a、路径和路径长度

若在一棵树中存在着一个结点序列 k1,k2,……,kj, 使得 ki是ki+1 的双亲(1<=i<j),则称此结点序列是从 k1 到 kj 的路径。

从 k1 到 kj 所经过的分支数称为这两点之间的路径长度,它等于路径上的结点数减1.


b、结点的权和带权路径长度

在许多应用中,常常将树中的结点赋予一个有着某种意义的实数,我们称此实数为该结点的权,(如下面一个树中的蓝色数字表示结点的权)

结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点上权的乘积。


c、树的带权路径长度

树的带权路径长度定义为树中所有叶子结点的带权路径长度之和,公式为:

 其中,n表示叶子结点的数目,wi 和 li 分别表示叶子结点 ki 的权值和树根结点到 ki 之间的路径长度。

如下图中树的带权路径长度 WPL = 9 x 2 + 12 x 2 + 15 x 2 + 6 x 3 + 3 x 4 + 5 x 4  =  122

d、哈夫曼树

哈夫曼树又称最优二叉树。它是 n 个带权叶子结点构成的所有二叉树中,带权路径长度 WPL 最小的二叉树。

如下图为一哈夫曼树示意图。

2、构造哈夫曼树


假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:


(1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);


(2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;


(3)从森林中删除选取的两棵树,并将新树加入森林;


(4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。


 如:对 下图中的六个带权叶子结点来构造一棵哈夫曼树,步骤如下:

  注意:为了使得到的哈夫曼树的结构尽量唯一,通常规定生成的哈夫曼树中每个结点的左子树根结点的权小于等于右子树根结点的权。


具体算法如下:

   

 //2、根据数组 a 中 n 个权值建立一棵哈夫曼树,返回树根指针 
  struct BTreeNode* CreateHuffman(ElemType a[], int n) 
  { 
    int i, j; 
    struct BTreeNode **b, *q; 
    b = malloc(n*sizeof(struct BTreeNode)); 
    for (i = 0; i < n; i++) //初始化b指针数组,使每个指针元素指向a数组中对应的元素结点 
    { 
      b[i] = malloc(sizeof(struct BTreeNode)); 
      b[i]->data = a[i]; 
      b[i]->left = b[i]->right = NULL; 
    } 
    for (i = 1; i < n; i++)//进行 n-1 次循环建立哈夫曼树 
    { 
      //k1表示森林中具有最小权值的树根结点的下标,k2为次最小的下标 
      int k1 = -1, k2; 
      for (j = 0; j < n; j++)//让k1初始指向森林中第一棵树,k2指向第二棵 
      { 
        if (b[j] != NULL && k1 == -1) 
        { 
          k1 = j; 
          continue; 
        } 
        if (b[j] != NULL) 
        { 
          k2 = j; 
          break; 
        } 
      } 
      for (j = k2; j < n; j++)//从当前森林中求出最小权值树和次最小 
      { 
        if (b[j] != NULL) 
        { 
          if (b[j]->data < b[k1]->data) 
          { 
            k2 = k1; 
            k1 = j; 
          } 
          else if (b[j]->data < b[k2]->data) 
            k2 = j; 
        } 
      } 
      //由最小权值树和次最小权值树建立一棵新树,q指向树根结点 
      q = malloc(sizeof(struct BTreeNode)); 
      q->data = b[k1]->data + b[k2]->data; 
      q->left = b[k1]; 
      q->right = b[k2]; 
   
      b[k1] = q;//将指向新树的指针赋给b指针数组中k1位置 
      b[k2] = NULL;//k2位置为空 
    } 
    free(b); //删除动态建立的数组b 
    return q; //返回整个哈夫曼树的树根指针 
  } 


3、哈夫曼编码

在电报通信中,电文是以二进制的0、1序列传送的,每个字符对应一个二进制编码,为了缩短电文的总长度,采用不等长编码方式,构造哈夫曼树,

将每个字符的出现频率作为字符结点的权值赋予叶子结点,每个分支结点的左右分支分别用0和1编码,从树根结点到每个叶子结点的路径上

所经分支的0、1编码序列等于该叶子结点的二进制编码。如上文所示的哈夫曼编码如下:

 a 的编码为:00

b 的编码为:01

c 的编码为:100

d 的编码为:1010

e 的编码为:1011

f 的编码为:11


4、哈夫曼树的操作运算


以上文的哈夫曼树作为具体实例,用详细的程序展示哈夫曼树的操作运算

 #include<stdio.h> 
 #include<stdlib.h> 
 typedef int ElemType; 
 struct BTreeNode 
 { 
  ElemType data; 
  struct BTreeNode* left; 
  struct BTreeNode* right; 
 }; 
  
 //1、输出二叉树,可在前序遍历的基础上修改。采用广义表格式,元素类型为int 
 void PrintBTree_int(struct BTreeNode* BT) 
 { 
  if (BT != NULL) 
  { 
   printf("%d", BT->data); //输出根结点的值 
   if (BT->left != NULL || BT->right != NULL) 
   { 
    printf("("); 
    PrintBTree_int(BT->left); //输出左子树 
    if (BT->right != NULL) 
     printf(","); 
    PrintBTree_int(BT->right); //输出右子树 
    printf(")"); 
   } 
  } 
 } 
  
 //2、根据数组 a 中 n 个权值建立一棵哈夫曼树,返回树根指针 
 struct BTreeNode* CreateHuffman(ElemType a[], int n) 
 { 
  int i, j; 
  struct BTreeNode **b, *q; 
  b = malloc(n*sizeof(struct BTreeNode)); 
  for (i = 0; i < n; i++) //初始化b指针数组,使每个指针元素指向a数组中对应的元素结点 
  { 
   b[i] = malloc(sizeof(struct BTreeNode)); 
   b[i]->data = a[i]; 
   b[i]->left = b[i]->right = NULL; 
  } 
  for (i = 1; i < n; i++)//进行 n-1 次循环建立哈夫曼树 
  { 
   //k1表示森林中具有最小权值的树根结点的下标,k2为次最小的下标 
   int k1 = -1, k2; 
   for (j = 0; j < n; j++)//让k1初始指向森林中第一棵树,k2指向第二棵 
   { 
    if (b[j] != NULL && k1 == -1) 
    { 
     k1 = j; 
     continue; 
    } 
    if (b[j] != NULL) 
    { 
     k2 = j; 
     break; 
    } 
   } 
   for (j = k2; j < n; j++)//从当前森林中求出最小权值树和次最小 
   { 
    if (b[j] != NULL) 
    { 
     if (b[j]->data < b[k1]->data) 
     { 
      k2 = k1; 
      k1 = j; 
     } 
     else if (b[j]->data < b[k2]->data) 
      k2 = j; 
    } 
   } 
   //由最小权值树和次最小权值树建立一棵新树,q指向树根结点 
   q = malloc(sizeof(struct BTreeNode)); 
   q->data = b[k1]->data + b[k2]->data; 
   q->left = b[k1]; 
   q->right = b[k2]; 
  
   b[k1] = q;//将指向新树的指针赋给b指针数组中k1位置 
   b[k2] = NULL;//k2位置为空 
  } 
  free(b); //删除动态建立的数组b 
  return q; //返回整个哈夫曼树的树根指针 
 } 
  
 //3、求哈夫曼树的带权路径长度 
 ElemType WeightPathLength(struct BTreeNode* FBT, int len)//len初始为0 
 { 
  if (FBT == NULL) //空树返回0 
   return 0; 
  else 
  { 
   if (FBT->left == NULL && FBT->right == NULL)//访问到叶子结点 
    return FBT->data * len; 
   else //访问到非叶子结点,进行递归调用,返回左右子树的带权路径长度之和,len递增 
    return WeightPathLength(FBT->left,len+1)+WeightPathLength(FBT->right,len+1); 
  } 
 } 
  
 //4、哈夫曼编码(可以根据哈夫曼树带权路径长度的算法基础上进行修改) 
 void HuffManCoding(struct BTreeNode* FBT, int len)//len初始值为0 
 { 
  static int a[10];//定义静态数组a,保存每个叶子的编码,数组长度至少是树深度减一 
  if (FBT != NULL)//访问到叶子结点时输出其保存在数组a中的0和1序列编码 
  { 
   if (FBT->left == NULL && FBT->right == NULL) 
   { 
    int i; 
    printf("结点权值为%d的编码:", FBT->data); 
    for (i = 0; i < len; i++) 
     printf("%d", a[i]); 
    printf("\n"); 
   } 
   else//访问到非叶子结点时分别向左右子树递归调用,并把分支上的0、1编码保存到数组a 
   { //的对应元素中,向下深入一层时len值增1 
    a[len] = 0; 
    HuffManCoding(FBT->left, len + 1); 
    a[len] = 1; 
    HuffManCoding(FBT->right, len + 1); 
   } 
  } 
 } 
  
 //主函数 
 void main() 
 { 
  int n, i; 
  ElemType* a; 
  struct BTreeNode* fbt; 
  printf("从键盘输入待构造的哈夫曼树中带权叶子结点数n:"); 
  while(1) 
  { 
   scanf("%d", &n); 
   if (n > 1) 
    break; 
   else 
    printf("重输n值:"); 
  } 
  a = malloc(n*sizeof(ElemType)); 
  printf("从键盘输入%d个整数作为权值:", n); 
  for (i = 0; i < n; i++) 
   scanf(" %d", &a[i]); 
  fbt = CreateHuffman(a, n); 
  printf("广义表形式的哈夫曼树:"); 
  PrintBTree_int(fbt); 
  printf("\n"); 
  printf("哈夫曼树的带权路径长度:"); 
  printf("%d\n", WeightPathLength(fbt, 0)); 
  printf("树中每个叶子结点的哈夫曼编码:\n"); 
  HuffManCoding(fbt, 0); 
 } 


运行结果:

下面来看一道ACM题目

    题目描述: 
    哈夫曼树,第一行输入一个数n,表示叶结点的个数。需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之和。 
    输入: 
    输入有多组数据。 
    每组第一行输入一个数n,接着输入n个叶节点(叶节点权值不超过100,2<=n<=1000)。 
    输出: 
    输出权值。 
    样例输入: 
    5   
    1 2 2 5 9 
    样例输出: 
    37 


ac代码

链表构建哈夫曼树(插入排序)

 #include <stdio.h> 
 #include <stdlib.h> 
 #define max 1001 
  
 struct htree 
 { 
  int weight; 
  struct htree *lchild; 
  struct htree *rchild; 
  struct htree *next; 
 }; 
  
 void addNode(struct htree *, struct htree *); 
 struct htree* createHfmtree(int *, int); 
 int getWpl(struct htree *, int); 
  
 int main() 
 { 
  int w[max]; 
  int i, n, wpl; 
  struct htree *ht; 
  
  while(scanf("%d", &n) != EOF) 
  { 
   for(i = 0; i < n; i ++) 
   { 
    scanf("%d", &w[i]); 
   } 
    
   ht = createHfmtree(w, n); 
   wpl = getWpl(ht, 0); 
   printf("%d\n", wpl); 
  } 
  return 0; 
 } 
  
 struct htree* createHfmtree(int *w, int n) 
 { 
  int i; 
  struct htree *head, *pl, *pr, *proot; 
  head = (struct htree *)malloc(sizeof(struct htree)); 
  head->next = NULL; 
  
  for(i = 0; i < n; i ++) 
  { 
   struct htree *pnode = malloc(sizeof(struct htree)); 
   pnode->weight = *(w + i); 
   pnode->lchild = pnode->rchild = pnode->next = NULL; 
   addNode(head, pnode); 
  } 
  
  while(head->next) 
  { 
   if(head->next->next == NULL) 
    break; 
   pl = head->next; 
   pr = pl->next; 
   head->next = pr->next; 
   proot = (struct htree *)malloc(sizeof(struct htree)); 
   proot->weight = pl->weight + pr->weight; 
   proot->lchild = pl; 
   proot->rchild = pr; 
   addNode(head, proot); 
  } 
  return head->next; 
 } 
  
 void addNode(struct htree *head, struct htree *pnode) 
 { 
  struct htree *t = head; 
  
  while(t->next && t->next->weight < pnode->weight) 
   t = t->next; 
  pnode->next = t->next; 
  t->next = pnode; 
 } 
  
 int getWpl(struct htree *ht, int level) 
 { 
  if(ht == NULL) 
   return 0; 
  if(!ht->lchild && !ht->rchild) 
  { 
   return ht->weight * level; 
  } 
  
  return getWpl(ht->lchild, level + 1) + getWpl(ht->rchild, level + 1); 
 } 



相关阅读:
asp.net判断字符串是否是中文的方法
MySQL中distinct与group by语句的一些比较及用法讲解
Android程序开发通过HttpURLConnection上传文件到服务器
PHP中类的继承和用法实例分析
各种AJAX方法的使用比较详解
win7升级win8系统后鼠标间歇性失灵如何解决
php微信支付之APP支付方法
win10预览版10061系统主题颜色怎么更改
Jquery实现仿腾讯微博发表广播
PHP 抽象方法与抽象类abstract关键字介绍及应用
使用配置类定义Codeigniter全局变量
WordPress主题制作之模板文件的引入方法
如何解决mysqlimport: Error: 13, Can't get stat of 的问题
快速解决owin返回json字符串多带了双引号"多了重string转义字符串
快速导航
PHP MySQL HTML CSS JavaScript MSSQL AJAX .NET JSP Linux Mac ASP 服务器 CMS SQL jQuery C# C++ java Android IOS oracle MongoDB PostgreSQL SQLite 交通频道 G4722 G1875 G215 G569 G421 G6733 G7577 G8906 G1235 G4916 G7291 G1953 G245 G662 G1570 G6285 G719 G1836 G1346 G4781 G4908 G289 G6781 G9290 G7358 G1928 G1815 G325 G132 G4901 G6012 G6290 G7131 G5367 G184 G151 G5303 G1136 G6481 G7028 G575 G1744 G7660 G7693 G2344 G4937 G1234 G1814 G6252 G1492 G253 G2926 G883 G9275 G1231 G556 G241 G1306 G7646 G8103 G600 G1858 G9678 G6160 G7156 G825 G1125 G7249 G1809 G1350 G432 G9466 G7067 G785 G6404 G4663 G7008 G150 G823 G1514 G7529 G1201 G2353 G205 G7629 G9409 G6147 G677 G390 G8016 G9239 G456 G828 G8045 G491 G7145 G397 G7012 G1021 G6482 G2322 G7264 G1301 G9247 G96 G1294 G7133 G4824 G7005 G1653 G5307 G1213 G822 G4837 G1422 G411 G6227 G1571 G359 G1882 G6074 G7678 G21 G7077 G1272 G8918 G9645 G461 G1254 G1846 G8021 G7303 G1104 G76 G82 G621 G218 G8533 G2341 G8543 G555 G8013 G4802 G1364 G1153 G1342 G1861 G8905 G590 G4780 G668 G9261 G1304 G1638 G1395 G2914 G8003 G7158 G1833 G1873 G8128 G1856 G1841 G8709 G7346 G4612 G2103 G835 G8712 G381 G7240 G8932 G507 G29 G4054 G6273 G6752 G426 G211 G9473 G7119 G2333 G1567 G6153 G360 G4011 G5301 G7648 G8010 G8015 G6706 G614 G423 G8557 G9465 G72 G6018 G8901 G7030 G123

丹东 云霄 辽中 德阳 克拉玛依 惠山 招远 昭通 铁岭西 延吉西 军粮城北 定西 晋中 许昌东 郫县 诏安 七台河 高碑店东 南昌 延安 敦化 铜陵北 嵩明 鲘门 扬中 龙里北 舟山 洛阳 运城北 鞍山 西昌 邵阳北 绍兴 白山 三明 肇东 陵水 衡山西 嘉善 宜都 泰兴 泉州 汉口 东胜西 昌图西 锦州南 安阳东 怀化 黄南 亚龙湾 扬州 温州 南翔北 福安 金山北 永川东 安达 曲阜东 郑州西 天门 绍兴北 涪陵北 阳泉北 三亚 葫芦岛北 徐州 阳江 辽源 新泰 阿坝 孝感北 三穗 金寨 保山 高安 安阳 牟平 西双版纳 信阳 繁昌西 哈尔滨北 达州 新余 沈阳南 四平 扶余北 伊宁 郴州西 济源 水家湖 民权北 福鼎 如皋 奉化 全州南 安庆 太姥山 武汉 乐清 皮口 武昌 茂名 邯郸 资阳 马鞍山 三水南 泰安 包头东 衡阳东 南丰 仙桃西 安吉 罗源 山海关 平湖 惠州 资阳北 淄博 丹阳 莱州 巴东 关岭 盐城 锦州 格尔木 益阳 大英东 吉林 湛江 临安 襄汾西 渑池南 当涂东 辽阳 徐水 贺州 韶关 光明城 邯郸东 普安县 南江口 铜川 五龙背东 张家港 烟台南 萍乡北 青堆 长乐 江门 台州 衡水 湘潭北 闽清北 高邑西 盖州西 石柱县 潮汕 肇庆 泰康 邵东 湖州 余姚 平凉 宜宾 增城 沧州 都匀 防城港 鹰潭北 海东西 福田 余姚北 岳池 广州北 南安 蓬莱 瓦房店西 李石寨 葛店南 海安 无锡东 上饶 通辽 四会 桂林西 砀山南 兰州 滨海 龙口 绅坊 莱西 石林西 深圳 大连北 成都 上海西 孝感 杏树屯 德清 嘉兴

Copyright © 2016 phpStudy |