C语言实现哈夫曼树的方法

本文实例为大家分享了C语言实现哈夫曼树的具体代码,供大家参考,具体内容如下

准备工作:

1、定义一个结构体,表示一个节点。其中,这个结构体有4个成员变量,分别表示是这个节点的权值,父节点及左右子节点的下标
2、定义一个整形数组,用于存放各个节点的权值
3、定义一个整形数组,用于存放哈夫曼编码,当然也可以定义一个整形数组来存放哈夫曼编码

构建哈夫曼树:

1、给这个哈夫曼树创建一个结构体数组,其中分配的空间是2 * n - 1,因为我们都知道哈夫曼树的性质有一个是:给定n个叶子节点,那么由这n个叶子节点构成 的哈夫曼树一共含有2 * n - 1个节点。
2、结构体数组前面n个用于存放n个叶子节点,然后后面的n - 1个节点用于存放父节点。这时候,我们需要遍历这个结构体数组,将所有的节点的进行初始化,即节点的权值就是结构体数组各个下标对应的值,然后节点的父节点及子节点的下标为-1,表示的是这个节点没有父节点,同时也没有子节点。
3、遍历数组,将获取数组中两个最小的叶子节点,然后将他们的权值合并构成一个新节点。在这一步中,我们同时需要知道这两个最小节点在结构体数组中的下标,只有这样,我们才可以知道它的父节点的左右子节点的下标,在初始化父节点的时候需要用到。
4、如果已经进行了n - 1次数操作,表明已经构建完成了。

获取哈夫曼编码:

1、由于我们将所有节点的权值都赋值给了一个数组,并且哈夫曼树中的节点的下标和这个数组的下标是一一对应的,那么我们只需要首先在数组中获取这个数字的下标,就表示他在哈夫满树中的下标也是这个,然后往它的父节点方向走,如果当前节点时它父节点的右子节点,那么就将1存放到数组arr2中,否则字符将0存放到数组arr2中。重复这一步,直到当前的节点的父节点为空,及已经遍历到了根节点。
2、重复步骤一,存放数字的数组已经遍历完了,这时候已经将所有数字的哈夫曼编码都已经输出了

#include<stdio.h>
#define MAX_SIZE 1000
typedef struct NODE Node;
struct NODE{
   int weight;//节点的权值
   int parent,lchild,rchild;
};
/*
初始化或者更改节点的信息,比如,如果这个节点是一个新节点,那么
就需要将这个节点初始化成一个叶子节点,否则需要修改这个节点的父节点
*/
void initNode(Node &node,int weight,int parent,int lchild,int rchild){
    node.weight = weight;
    node.lchild = lchild;
    node.rchild = rchild;
    node.parent = parent;
}
/*
1、有n个叶子节点,那么构建哈夫曼树的时候,需要分配n * 2 - 1个内存空间,前n
个表示的是新输入的叶子节点,后面n - 1表示的是叶子节点的父节点
2、遍历这个数组,将进行初始化,即给这些节点的权值赋值,并且将他的左右子节
点、父节点赋初始值为-1,从而构建了n个叶子节点
3、遍历数组,从而将从这个数组中跳出两个值最小的叶子节点,同时需要标记他们的下标,从而可以知道当前最小值节点的父节点的左右子节点的下标,方便下次寻找
最小值的叶子结点的时候不会再找到已经找过的叶子节点
4、将新节点插入到数组的最后。
5、重复3,4的操作,直到只有一个节点,那么这个节点就是哈夫曼树的根节点
*/
void createHuffmanTree(Node *node,int *arr,int n){
    //n表示有n个叶子节点,arr数组存放的是所有叶子节点的值
   int i,j,min1,min2,x1,x2,total;//min1:第一个最小值,min2:第二个最小值,x1:第一个最小值的下标,x2:第二个最小值的下标
   for(i = 0; i < n; i++){
       initNode(node[i],arr[i],-1,-1,-1);//调用initNode方法,从而将节点进行初始化
   }
   total = n * 2 - 1;//total表示的是哈夫曼所有节点的个数
   for(i = n; i < total; i++){
        //i之所以从n开始,是因为第一个父节点这个下标(前n个节点是叶子节点)
        min1 = 65432;//定义两个最小值
        min2 = min1;
        x1 = x2 = 0;//假设两个最小值的下标都是0
        for(j = 0; j < i; j++){
            //判断当前下标的节点是否为叶子节点
           if(node[j].parent == -1){
          //如果当前节点的parent等于-1,表示这个节点是一个叶子节点,那么我们需要判断他是否一个最小节点
                if(node[j].weight < min1){
         //如果当前这个节点的值比min1小,那么我们需要更新min2,min1,同时需要更新两者对应的下标
                    min2 = min1;
                    x2 = x1;
                    min1 = node[j].weight;
                    x1 = j;
                }else if(node[j].weight < min2){
                 /*
                 如果当前这个节点比第一个最小值要大,那么我们需要判断
                 他是否比第二个最小值小,如果是,那么更新min2,并且更新x2
                 */
                   min2 = node[j].weight;
                   x2 = j;
                }
           }
        }
        /*
        找到两个最小节点之后,我们需要将这两个节点的父节点指向i,
        然后将i这个节点进行初始化,并且新节点的左子节点比右子节点小
        从而构建唯一的哈夫曼树
        */
        node[x1].parent = i;
        node[x2].parent = i;
        initNode(node[i],min1 + min2,-1,x1,x2);//初始化合并之后的新节点
   }
}
void huffmanCode(Node *node,int child,int *str){
    //str表示的是这个叶子节点的哈夫曼编码
    int i,parent,j = 0,e;
    parent = node[child].parent;//获取当前这个叶子节点的父节点
    while(parent != -1){
        if(node[parent].lchild == child){
            //如果当前这个节点是父节点的左子节点,那么就将0压入到数组中,否则将1压入数组中
            str[j++] = 0;
        }else{
            str[j++] = 1;
        }
        child = parent;
        parent = node[child].parent;
    }
    e = j;//当退出循环的时候,j表示的是这个数的哈夫曼编码的长度,所以需要从下标为j - 1开始逆序输出,才是这个数的哈夫曼编码
    for(j = e - 1; j>= 0; j--)
        printf("%d",str[j]);
    printf("\n");
}
int main(){
  Node node[MAX_SIZE];
  int arr[MAX_SIZE];//定义一个整形数组,用于存放所有叶子节点的权值
  int arr2[MAX_SIZE];//arr2用于存放一个数字的哈夫曼编码
  int n,i,j,e;
  printf("请输入叶子节点的个数:");
  scanf("%d",&n);
  for(i = 0; i < n; i++)
    scanf("%d",&arr[i]);
  createHuffmanTree(node,arr,n);//构建哈夫曼树
  /*
  获取哈夫曼编码:
  1、将遍历数组arr,从而获得各个叶子节点的权值以及下标
  2、通过这个下标,我们从这个节点向根节点走去,如果当前节点是父节点的左子
  节点,那么将0压入到数组中,否则将1压入到数组arr2中
  3、逆序输出arr2
  */
  for(i = 0; i < n; i++){
    huffmanCode(node,i,arr2);//调用这个方法,将当前下标对应的数字的哈夫曼编码输出
  }
  return 0;
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

时间: 2021-05-03

C语言实现哈夫曼树

本文实例为大家分享了C语言实现哈夫曼树的具体代码,供大家参考,具体内容如下 //哈夫曼树C语言实现 #include <stdio.h> #include <stdlib.h> typedef struct HuffmanNode { char letter;//存储的字符,叶节点为字母,非叶节点为# struct HuffmanNode *parent;//父亲结点 int code;//如果为父亲结点的左孩子,则为0,右孩子为1 }HuffmanNode; typedef st

C语言实现哈夫曼树的构建

哈夫曼树(霍夫曼树)又称为最优树. 1.路径和路径长度 在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径.通路中分支的数目称为路径长度.若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1. 2.结点的权及带权路径长度 若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权.结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积. 3.树的带权路径长度 树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为WPL #include

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

1.基本概念 a.路径和路径长度 若在一棵树中存在着一个结点序列 k1,k2,--,kj, 使得 ki是ki+1 的双亲(1<=i<j),则称此结点序列是从 k1 到 kj 的路径. 从 k1 到 kj 所经过的分支数称为这两点之间的路径长度,它等于路径上的结点数减1. b.结点的权和带权路径长度 在许多应用中,常常将树中的结点赋予一个有着某种意义的实数,我们称此实数为该结点的权,(如下面一个树中的蓝色数字表示结点的权) 结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点上权的乘

C语言实现哈夫曼编码

本文实例为大家分享了C语言实现哈夫曼编码的具体代码,供大家参考,具体内容如下 代码来自于<小甲鱼C++快速入门> 主程序main.cpp #include "stdafx.h" #include <stdlib.h> #include "huffman.h" int main() { htTree *codeTree = buildTree("I love wwwwwwwwwFishC.com!");//建立哈夫曼树 hl

C++实现哈夫曼树简单创建与遍历的方法

本文以实例形式讲述了C++实现哈夫曼树简单创建与遍历的方法,比较经典的C++算法. 本例实现的功能为:给定n个带权的节点,如何构造一棵n个带有给定权值的叶节点的二叉树,使其带全路径长度WPL最小. 据此构造出最优树算法如下: 哈夫曼算法: 1. 将n个权值分别为w1,w2,w3,....wn-1,wn的节点按权值递增排序,将每个权值作为一棵二叉树.构成n棵二叉树森林F={T1,T2,T3,T4,...Tn},其中每个二叉树都只有一个权值,其左右字数为空 2. 在森林F中选取根节点权值最小二叉树,

C++数据结构之文件压缩(哈夫曼树)实例详解

C++数据结构之文件压缩(哈夫曼树)实例详解 概要: 项目简介:利用哈夫曼编码的方式对文件进行压缩,并且对压缩文件可以解压 开发环境:windows vs2013 项目概述:         1.压缩 a.读取文件,将每个字符,该字符出现的次数和权值构成哈夫曼树 b.哈夫曼树是利用小堆构成,字符出现次数少的节点指针存在堆顶,出现次数多的在堆底 c.每次取堆顶的两个数,再将两个数相加进堆,直到堆被取完,这时哈夫曼树也建成 d.从哈夫曼树中获取哈夫曼编码,然后再根据整个字符数组来获取出现了得字符的编

图文详解JAVA实现哈夫曼树

前言  我想学过数据结构的小伙伴一定都认识哈夫曼,这位大神发明了大名鼎鼎的"最优二叉树",为了纪念他呢,我们称之为"哈夫曼树".哈夫曼树可以用于哈夫曼编码,编码的话学问可就大了,比如用于压缩,用于密码学等.今天一起来看看哈夫曼树到底是什么东东. 概念 当然,套路之一,首先我们要了解一些基本概念. 1.路径长度:从树中的一个结点到另一个结点之间的分支构成这两个结点的路径,路径上的分支数目称为路径长度. 2.树的路径长度:从树根到每一个结点的路径长度之和,我们所说的完全

解读赫夫曼树编码的问题

定义: 结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积.树的带权路径长度为树中所有叶子结点的带权路径长度之和.假设有n个权值,试构造一棵有n个叶子结点的二叉树,每个叶子结点带权为wi,则其中带权路径长度最小的二叉树称做最优二叉树或赫夫曼树. 构造赫夫曼树的方法: (1)根据给定的n个权值{w1,w2,w3......}构成n棵二叉树的集合F={T1,T2,T3,T4......},其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树均空. (2)在F中选取两棵根结点的权值

C++ 哈夫曼树对文件压缩、加密实现代码

在以前写LZW压缩算法的时候,遇到很多难受的问题,基本上都在哈夫曼编码中解决了,虽然写这代码很费神,但还是把代码完整的码出来了,毕竟哈夫曼这个思想确实很牛逼.哈夫曼树很巧妙的解决了当时我在LZW序列化的时候想解决的问题,就是压缩后文本的分割.比如用lzw编码abc,就是1,2,3.但这个在存为文件的时候必须用分割符把1,2,3分割开,非常浪费空间,否则会和12 23 123 产生二义性.而哈夫曼树,将所有char分布在叶节点上,在还原的时候,比如1101110,假设110是叶节点,那么走到110

java哈夫曼树实例代码

本文实例为大家分享了哈夫曼树java代码,供大家参考,具体内容如下 package boom; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Queue; class Node<T> implements Comparable<Node<T>>{ private T