【数据结构】哈夫曼树

哈夫曼树性质

哈夫曼树构造原理

（2）重复过程1，直到n变为1；

（3）有上述构造的过程可知，哈夫曼树没有度为1的节点；若有n个叶子节点的哈夫曼树共有2n-1个结点；

哈夫曼树编码

（1）任何一个字符的编码都不是另一个字符的编码前缀，我们称为前缀编码；比如110不是011的前缀，11是110的前缀；

（2）将哈夫曼树的左右子树按照约定依次编号为0和1，即可得到一个编码树；

（3）对于上述哈夫曼树，给定的二进制序列如0222220010解码为ADCAB；而对于BDADCAB我们编码二进制序列为101110222220010；

完整代码

说明几点

（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----->%.2fn",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 

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!