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

哈夫曼树(霍夫曼树)又称为最优树.

1、路径和路径长度

在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1。

2、结点的权及带权路径长度

若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积。

3、树的带权路径长度

树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为WPL

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* 哈夫曼树的结构体 */
typedef struct stHuNode
{
  int data; //权值
  struct stHuNode* lchild, *rchild;
}HUNODE;

/*
* 找出权值数组里面,最小的两个权值下标
* 函数请参:HUNODE *pArray[] 存放节点的指针数组
      int n 数组里面的元素个数
      int* p1 存放最小权值的下标
      int* p2 存放第二小权值的下标
*/
int findSmallData(HUNODE *pArray[] ,int n,int* p1, int* p2)
{
  int index = 0;
  int fir_small = 0xffff, sec_small = 0xffff;

  if(pArray == NULL)
  {
    return 1;
  }

  for(index = 0; index < n; index++)
  {
    /* 当前的下标下面是有节点的*/
    if(pArray[index] != NULL)
    {
      if(pArray[index]->data < fir_small)
      {
        sec_small = fir_small;
        fir_small = pArray[index]->data;

        *p2 = *p1;
        *p1 = index;
      }
      else if(pArray[index]->data < sec_small)
      {
        sec_small = pArray[index]->data;
        *p2 = index;
      }
    }
  }

  return 0;
}
/*
* 函数功能:构建哈夫曼树
* 函数请参:int* a 权值数组
      int n 这个数组里面有多少个数据
*/

HUNODE* createHuTree(int* a, int n)
{
  int index = 0;

  int fir_small = 0, sec_small = 0;

  /* 定义一个指针数组,最大是100 */
  HUNODE *pArray[100];
  HUNODE *pNewNode = NULL;

  /* 先创建n个root节点*/
  memset(pArray,0,sizeof(HUNODE)*n);
  for(index = 0; index < n; index++)
  {
    pNewNode = (HUNODE*)malloc(sizeof(HUNODE));
    memset(pNewNode,0,sizeof(HUNODE));

    pNewNode->data = a[index];
    pNewNode->lchild = NULL;
    pNewNode->rchild = NULL;

    /* 把这个节点存放在指针数组中去 */
    pArray[index] = pNewNode;
  }

  /* 构建哈夫曼树 */
  for(index = 0; index < n-1; index++)
  {
    /* fir_small 存放最小权值的下标 sec_small存放第二个小的权值下标*/
    findSmallData(pArray,n,&fir_small,&sec_small);

    /* 分配节点内存 */
    pNewNode = (HUNODE*)malloc(sizeof(HUNODE));
    memset(pNewNode,0,sizeof(HUNODE)); 

    pNewNode->data = pArray[fir_small]->data + pArray[sec_small]->data;

    /* 最小的是左孩子,第二小的是右孩子 */
    pNewNode->lchild = pArray[fir_small];
    pNewNode->rchild = pArray[sec_small];

    /* 把新的节点放入到指针数组里面去 */
    pArray[fir_small] = NULL;
    pArray[sec_small] = pNewNode;

  }
  return pNewNode;
}

/* 前序遍历该二叉树 */
void preOrderHuffMan(HUNODE* root)
{
  if(root)
  {
    printf("%d ",root->data);
    preOrderHuffMan(root->lchild);
    preOrderHuffMan(root->rchild);
  }
}

int main()
{
  int a[4] = {7,5,2,4};
  HUNODE* root = NULL;

  /* 构建哈夫曼树 */
  root = createHuTree(a,4);

  /* 前序遍历 */
  preOrderHuffMan(root);
  printf("\n");

  return 0;
}

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

(0)

相关推荐

  • 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语言实现哈夫曼树的方法

    本文实例为大家分享了C语言实现哈夫曼树的具体代码,供大家参考,具体内容如下 准备工作: 1.定义一个结构体,表示一个节点.其中,这个结构体有4个成员变量,分别表示是这个节点的权值,父节点及左右子节点的下标 2.定义一个整形数组,用于存放各个节点的权值 3.定义一个整形数组,用于存放哈夫曼编码,当然也可以定义一个整形数组来存放哈夫曼编码 构建哈夫曼树: 1.给这个哈夫曼树创建一个结构体数组,其中分配的空间是2 * n - 1,因为我们都知道哈夫曼树的性质有一个是:给定n个叶子节点,那么由这n个叶子

  • 基于C语言利用哈夫曼树实现文件压缩的问题

    一.哈夫曼树 具有n个权值的n个叶子结点,构造出一个二叉树,使得该树的带权路径长度(WPL)最小,则称此二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree). 注意:哈夫曼树是带权路径长度最短的树,且权值越大的叶子结点离根结点越近. 二.哈夫曼编码         哈夫曼编码是一种编码方式,又称"霍夫曼编码",其是可变字长的编码(VCL)的一种,是由霍夫曼于1952年提出的一种编码方式,有时被称为最佳编码,一般称为Huffman编码. 那么我们为什么要使用哈夫曼编码进行压缩?

  • 漫谈C++哈夫曼树的原理及实现

    目录 1. 前言 2. 设计思路 3. 构建思路 4. 编码实现 4.1 使用优先队列 4.2 使用一维数组 5. 总结 1. 前言 什么是哈夫曼树? 把权值不同的n个结点构造成一棵二叉树,如果此树满足以下几个条件: 此 n 个结点为二叉树的叶结点 . 权值较大的结点离根结点较近,权值较小的结点离根结点较远. 该树的带权路径长度是所有可能构建的二叉树中最小的. 则称符合上述条件的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree). 构建哈夫曼树的目的是什么? 用来解决在通信系统中如何

  • 使用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.树的路径长度:从树根到每一个结点的路径长度之和,我们所说的完全

随机推荐