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("
");

  return 0;
}

이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.