【数据结构】哈夫曼树

前端之家收集整理的这篇文章主要介绍了【数据结构】哈夫曼树前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
哈夫曼树,又称最优二叉树,它有着广泛的应用,尤其在数据压缩上;使用哈夫曼树的编码原理又称哈夫曼编码;

哈夫曼树性质

(1)路径长度:路径上的分支数目;
(2)树的路径长度:树根到每一个结点的路径长度之和;
(3)树的带权路径长度:树中所有叶子结点的带权路径长度之和,记为WPL = sum(Wk * Lk);

哈夫曼树构造原理


(1)哈夫曼树的构造过程,典型的使用了 贪心算法,即我们总是选择n的权值集合中,两颗最小的权值作为左右子树成为一颗新的二叉树节点,并放入新的权值集合中,此时n变为n-1;

(2)重复过程1,直到n变为1;

(3)有上述构造的过程可知,哈夫曼树没有度为1的节点;若有n个叶子节点的哈夫曼树共有2n-1个结点

哈夫曼树编码

(1)任何一个字符的编码都不是另一个字符的编码前缀,我们称为前缀编码;比如110不是011的前缀,11是110的前缀;

(2)将哈夫曼树的左右子树按照约定依次编号为0和1,即可得到一个编码树;


(3)对于上述哈夫曼树,给定的二进制序列如0111110010解码为ADCAB;而对于BDADCAB我们编码二进制序列为101110111110010;



完整代码

说明几点

(1)本代码使用双向链表形式进行对哈夫曼节点进行组织,将所有的链表中按节点值升序排序,每次只需要取链表的前两个节点,然后构造出一个新的节点,根据它的节点值插入到链表中,直到链表为只含一个节点为止;链表形式构造的哈夫曼树,时间复杂度为O(n*n);

(2)在哈夫曼节点嵌入双向循环链表节点中,即使用Linux中典型的链表构造方式;

(3)输入:随机生成一组哈夫曼节点概率;(注:链表头结点可使插入的情况一致,否则还要有头结点插入的特殊情况);

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

#define offsetof(TYPE,MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

#define container_of(ptr,type,member)({\
	const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
                       (type *)( (char *)__mptr - offsetof(type,member) );})

char code[] = {'A','B','C','D','E','F','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V'};

struct ListHead
{
  struct ListHead *next;
  struct ListHead *prev;
};

struct HaffmanNode
{
  int weight;
  struct HaffmanNode *left;
  struct HaffmanNode *right;

  struct ListHead list;
};

int generateSequence(int *probability)
{
  srand( (unsigned)time( NULL));
  int count = 0;
  int sum = 100;
  while (true)
    {
      int temp = 1 << (rand() % 6);

      if (temp < sum)
        {
          probability[count++] = temp;
          sum -= temp;
        }
      else
        {
          probability[count++] = sum;
          break;
        }
    }
  return count;
}

void initListHead(struct ListHead *head)
{
  head->next = head;
  head->prev = head;
}

struct ListHead*  listQueryPiror(int weight,struct ListHead *head)
{
  struct ListHead *node = head->next;
  while (node != head)
    {
      struct HaffmanNode *value = container_of(node,struct HaffmanNode,list);

      if (value->weight > weight)
        {
          return node->prev;
        }
      node = node->next;
    }

  return head->prev;
}

void listInsert(struct ListHead *node,struct ListHead *head)
{
  struct ListHead *pos;
  if (head->prev == head)
    {
      pos = head;
    }
  else
    {
      struct HaffmanNode *temp = container_of(node,list);
      pos = listQueryPiror(temp->weight,head);
    }

  node->next = pos->next;
  node->prev = pos;
  pos->next->prev = node;
  pos->next = node;
}

void listDelete(struct ListHead *node)
{
  node->next->prev = node->prev;
  node->prev->next = node->next;
}

void createHaffmanTree(struct ListHead *head)
{
  while (head  != head ->next->next)
    {
      struct HaffmanNode *value = (struct HaffmanNode *) malloc(sizeof(struct HaffmanNode));
      if (value == NULL)
        break;

      struct HaffmanNode *temp = container_of(head->next,list);
      value->weight = temp->weight;
      value->left = temp;
      listDelete(&temp->list);

      temp = container_of(head->next,list);
      value->weight += temp->weight;
      value->right = temp;
      listDelete(&temp->list);

      listInsert(&value->list,head);
    }
}

struct ListHead * createHaffmanNode(int* probability,int num)
{
  struct ListHead *head = (struct ListHead *)malloc(sizeof(struct ListHead));
  initListHead(head);

  for (int i = 0; i < num; i++)
    {
      struct HaffmanNode *value = (struct HaffmanNode *)malloc(sizeof(struct HaffmanNode));
      if (value == NULL)
        break;

      value->weight= probability[i];
      value->left = NULL;
      value->right = NULL;
      listInsert(&value->list,head);
    }

  createHaffmanTree(head);

  return head;
}


void displayHaffmanTree(struct HaffmanNode *root,int level)
{
  if (root != NULL)
    {
      displayHaffmanTree(root->left,level+1);
      printf("\n");
      int i;
      for (i = 0; i < level -1; i++)
        printf("   ");

      printf("%.2f ",root->weight * 0.01);

      displayHaffmanTree(root->right,level+1);
    }
}

void printfSequence(int* probability,int num)
{
  printf("------------------------\n");
  printf("leaf node and probability as follows:\n");
  for (int i = 0; i < num; i++)
    printf("%c----->%.2f\n",code[i],probability[i] * 0.01);
}


void freeHaffmanNode(struct HaffmanNode *node)
{
  if (node !=NULL)
    {
      freeHaffmanNode(node->left);
      freeHaffmanNode(node->right);
      free(node);
    }
}

void freeMem(struct ListHead *head)
{
  struct HaffmanNode *temp = container_of(head->next,list);
  free(head);
  freeHaffmanNode(temp);
}

int main(void)
{
  int probability[100];
  int num = generateSequence(probability);
  printfSequence(probability,num);

  struct ListHead* head = createHaffmanNode(probability,num);

  printf("\nhaff man list tree display as follows:\n");
  displayHaffmanTree(container_of(head->next,list),1);
  printf("\n");
  
  freeMem(head);
  return 0;
}

输出
sykpour@sykpour:~/Desktop$ gcc -o test test.cc
sykpour@sykpour:~/Desktop$ ./test
------------------------
leaf node and probability as follows:
A----->0.01
B----->0.32
C----->0.32
D----->0.04
E----->0.04
F----->0.08
H----->0.19

haff man list tree display as follows:

         0.08 
      0.17 
            0.04 
         0.09 
               0.01 
            0.05 
               0.04 
   0.36 
      0.19 
1.00 
      0.32 
   0.64 
      0.32 
原文链接:https://www.f2er.com/datastructure/382668.html

猜你在找的数据结构相关文章