데이터 구조와 알고리즘(7) 하프만 트리(Huffman)와 하프만 인코딩
1155 단어 데이터 구조와 알고리즘
하프만 나무는 최우수 두 갈래 나무라고도 불리며 대권 경로의 길이가 가장 짧은 두 갈래 나무이다.트리의 리본 경로 길이란 트리에 있는 모든 잎 결점의 값을 루트 결점까지의 경로 길이에 곱한 값입니다. (루트 결점이 0층이면 잎 결점에서 루트 결점까지의 경로 길이는 잎 결점의 층수입니다.)나무의 경로 길이는 나무 뿌리에서 매 결점까지의 경로 길이의 합으로 WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln), N개의 권한 Wi(i=1, 2,...n)로 N개의 잎결점이 있는 두 갈래 나무를 구성하고 해당하는 잎결점의 경로 길이는 Li(i=1, 2,...n)이다
2. 알고리즘 구현
#include
#include
//
struct huffmannode
{
int weight;
int tag,LeftChild,RightChild;
};
typedef struct huffmannode Huffmannode;
void InitHuffmannode(Huffmannode *h,int t,int l,int r)
{
h->tag=t;
h->LeftChild=l;
h->RightChild=r;
}
struct huffmantree
{
int root;
};
typedef struct huffmantree Huffmantree;
void InitHuffmantree(Huffmantree *ht,int r)
{
ht->root=r;
}
//
void makeHuffmantree(Huffmantree *ht,int a[],Huffmannode b[],int n)
{
int i,j,m1,m2,x1,x2;
// Huffman */
for(i=0; iroot=2*n-2;
}
// ( 0 1)
int main()
{
printf(" ( 0
");
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
두 갈래 나무의 깊이가 두루 다니다텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
