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

  • 更新时间:2022-08-01 09:55:06
  • 编辑:慎和豫
给大家整理了C语言相关的编程文章,网友张文虹根据主题投稿了本篇教程内容,涉及到C语言、霍夫曼树、C语言详解霍夫曼树相关内容,已被540网友关注,内容中涉及的知识点可以在下方直接下载获取。

参考资料

正文内容

C语言详解霍夫曼树

1、基本概念


a、路径和路径长度

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

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


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

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

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


c、树的带权路径长度

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

2015816155922684.jpg (314×123)

 其中,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 最小的二叉树。

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

2015816155310262.png (672×652)

2、构造哈夫曼树


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


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


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


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


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


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

2015816155522204.png (1140×1318)

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


具体算法如下:

   

 //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编码序列等于该叶子结点的二进制编码。如上文所示的哈夫曼编码如下:

2015816155607502.png (672×652)

 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); 
 } 


运行结果:

2015816155632294.png (555×288)

 

下面来看一道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); 
 } 

 

C语言相关教程

  • C语言程序中对二叉树数据结构的各种遍历方式

    这篇文章主要介绍了举例讲解C语言程序中对二叉树数据结构的各种遍历方式,先序中序后序二叉树遍历几乎成了最老生常谈的数据结构基础知识,的朋友可以参考下

    发布时间:2021-05-22

  • C语言链表实现销售管理系统

    C语言链表实现销售管理系统

    给网友朋友们带来一篇关于C语言的教程,这篇文章主要为大家详细介绍了C语言链表实现销售管理系统,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

    发布时间:2022-06-26

  • Linux中使用C语言的fork()函数创建子进程的实例教程

    Linux中使用C语言的fork()函数创建子进程的实例教程

    给大家整理了关于C语言的教程,fork是一个在Linux系统环境下专有的函数,现有的进程调用fork后将会创建一个新的进程,这里我们就来看一下Linux中使用C语言的fork()函数创建子进程的实例教程

    发布时间:2022-07-25

  • C语言中strcmp的实现原型

    给大家整理一篇关于C语言的教程,这篇文章主要介绍了C语言中strcmp的实现原型的相关资料,这里提供实例帮助大家理解这部分内容,希望能帮助到大家,需要的朋友可以参考下

    发布时间:2022-06-27

  • c语言和python之间有什么区别

    c语言和python之间有什么区别

    为网友们分享了关于python的教程,c语言和python之间的主要区别是:Python是一种面向对象的解释型语言,通过缩进来表示语句体,在Python中每一条语句结尾后没有分号;C是一种面向过程的编译型语言,通过{}来表示语句体,C语言

    发布时间:2022-06-22

  • C语言文件操作总结

    本篇文章给大家通过代码示例讲述了C语言文件操作的相关知识点,对此有兴趣的朋友可以参考学习下。

    发布时间:2022-04-06

  • C语言实现C++继承和多态的实例内容

    本文主要给大家简单讲诉了C和C++的区别以及如何使用C语言模拟实现C++继承和多态,并附上示例代码,是篇相当不错的文章,推荐给喜欢C语言的小伙伴们

    发布时间:2021-06-10

  • python是c语言开发的吗

    python是c语言开发的吗

    给网友们整理关于python的教程,python是c语言开发的。Python本身被设计为可扩展的,并非所有的特性和功能都集成到语言核心,Python提供了丰富的API和工具,以便程序员能够轻松地使用C、C++、Cython来编写扩展模块。

    发布时间:2022-07-07

  • 深入理解C语言指针

    为网友们分享了关于C语言的教程,关于指针,其是C语言的重点,C语言学的好坏,其实就是指针学的好坏。其实指针并不复杂,学习指针,要正确的理解指针

    发布时间:2022-06-22

  • C语言多线程服务器的实现实例

    C语言多线程服务器的实现实例

    给网友们整理关于C语言的教程,这篇文章主要介绍了C语言多线程服务器的实现实例,文章用实例讲解的很清楚,有对这方面不太懂的同学可以参考下

    发布时间:2022-07-12

用户留言