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


/* 哈夫曼樹的結(jié)構(gòu)體 */
typedef struct stHuNode
{
  int data; //權值
  struct stHuNode* lchild, *rchild;
}HUNODE;


/*
* 找出權值數(shù)組里面,最小的兩個權值下標
* 函數(shù)請參：HUNODE *pArray[] 存放節(jié)點的指針數(shù)組
      int n 數(shù)組里面的元素個數(shù)
      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++)
  {
    /* 當前的下標下面是有節(jié)點的*/
    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;
}
/*
* 函數(shù)功能：構(gòu)建哈夫曼樹
* 函數(shù)請參：int* a 權值數(shù)組
      int n 這個數(shù)組里面有多少個數(shù)據(jù)
*/

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

  int fir_small = 0, sec_small = 0;

  /* 定義一個指針數(shù)組,最大是100 */
  HUNODE *pArray[100];
  HUNODE *pNewNode = NULL;


  /* 先創(chuàng)建n個root節(jié)點*/
  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;

    /* 把這個節(jié)點存放在指針數(shù)組中去 */
    pArray[index] = pNewNode;
  }

  /* 構(gòu)建哈夫曼樹 */
  for(index = 0; index < n-1; index++)
  {
    /* fir_small 存放最小權值的下標 sec_small存放第二個小的權值下標*/
    findSmallData(pArray,n,&fir_small,&sec_small);

    /* 分配節(jié)點內(nèi)存 */
    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];

    /* 把新的節(jié)點放入到指針數(shù)組里面去 */
    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;

  /* 構(gòu)建哈夫曼樹 */
  root = createHuTree(a,4);

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

  return 0;
}