헤 프 만 트 리 인 코딩 문제 해독
결점 의 대역 권 경로 길 이 는 이 결점 에서 나무 뿌리 사이 의 경로 길이 와 결점 상권 의 곱셈 이다.나무의 권한 경로 길 이 는 나무의 모든 잎 결점 의 권한 경로 길이 의 합 이다.n 개의 가중치 가 있다 고 가정 하고 n 개의 잎 결점 이 있 는 이 진 트 리 를 구 조 했 습 니 다.모든 잎 결점 의 띠 권 은 wi 이 고 그 중에서 띠 권 경로 의 길이 가 가장 작은 이 진 트 리 를 가장 좋 은 이 진 트 리 나 헤 프 만 트 리 라 고 합 니 다.
헤 프 만 나 무 를 만 드 는 방법:
(1)주어진 n 개의 가중치{w1,w2,w3...}에 따라 n 개의 이 진 트 리 의 집합 F={T1,T2,T3,T4...}을 구성 합 니 다.
(2)F 에서 두 그루 의 뿌리 결산 점 의 가중치 가 가장 작은 나 무 를 선택 하여 좌우 나무 로 새로운 이 진 트 리 를 구성 하고 새로운 이 진 트 리 의 뿌리 결산 점 의 가중치 는 왼쪽,오른쪽 나무 위의 뿌리 결산 점 의 가중치 의 합 이다.
(3)F 에서 이 두 그루 의 나 무 를 삭제 하고 새로 얻 은 이 진 트 리 를 F 에 넣는다.
(4)F 가 나무 한 그루 만 포함 할 때 까지(2)와(3)을 반복 한다.이 나무 가 바로 헤 프 만 나무 다.
코드 구현:
#include<iostream>
#include<assert.h>
using namespace std;
struct HuffmanNode
{
unsigned int weight;
unsigned int parent,leftChild,rightChild;
HuffmanNode()
{
weight=0;parent=0;leftChild=0;rightChild=0;
}
};
void Select(const HuffmanNode* & nodelist,const int length,int & a, int &b)
{
int min=1000000,min2=1000000;
for(int i=0;i<length;i++)
{
if(min>nodelist[i].weight&&nodelist[i].parent==0)
{
min=nodelist[i].weight;
a=i;
}
}
for(int j=0;j<length;j++)
{
if(j!=a&&min2>nodelist[j].weight&&nodelist[j].parent==0)
{
min2=nodelist[j].weight;
b=j;
}
}
}
char ** HuffmanCoding(const int *w, const int n)
{
assert(w!=NULL);
int i,min1,min2;
int m = 2*n-1;
HuffmanNode * nodelist = new HuffmanNode[m]();
for(i=0;i<n;i++)
{
nodelist[i].weight=w[i];
nodelist[i].parent=0;
}
for(i=n;i<m;i++)
{
Select(nodelist,i,min1,min2);
nodelist[min1].parent=i;
nodelist[min2].parent=i;
nodelist[i].weight=nodelist[min1].weight+nodelist[min2].weight;
nodelist[i].rightChild=min2;
nodelist[i].leftChild=min1;
nodelist[i].parent=0;
}
char temp [20];
char ** code = new char * [n];
for(i=0;i<n;i++)
{
int j=i;
int index=0;
while(j!=m-1)
{
if(j==nodelist[nodelist[j].parent].leftChild) temp[index++]='0';
else temp[index++]='1';
j=nodelist[j].parent;
}
temp[index]='\0';
code[i] = new char[index+1];
strcpy(code[i],temp);
}
delete nodelist;
return code;
}
int main()
{
const int size=6;
char word[size]={'A','B','C','D','E','F'};//
int w[size]={4,3,2,1,7,8};//
char ** code;
code=HuffmanCoding(w,size);
assert(code!=NULL);
for(int i=0;i<size;i++)
{
cout<<word[i]<<" is coded as "<<code[i]<<endl;
}
//
for(int j=0;j<size;j++)
{
delete []code[j];
}
delete []code;
return 0;
}