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

哈夫曼树（霍夫曼树）又称为最优树.

1、路径和路径长度

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

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

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

3、树的带权路径长度

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

#include 
#include 
#include 



typedef struct stHuNode
{
  int data; //权值
  struct stHuNode* lchild, *rchild;
}HUNODE;



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


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

  int fir_small = 0, sec_small = 0;

  
  HUNODE *pArray[100];
  HUNODE *pNewNode = NULL;


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

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持考高分网。