[데이터 구조] 하프 만 트 리 와 하프 만 인 코딩 디 코딩

1. 원리:
1.      하 프 만 트 리: n 개의 가중치 를 n 개의 잎 결점 으로 정 하고 이 진 트 리 를 구성 합 니 다. 만약 에 권한 을 가 진 경로 의 길이 가 가장 작 으 면 이런 이 진 트 리 를 가장 좋 은 이 진 트 리 라 고 부 르 고 하 프 만 트 리 (Huffman Tree) 라 고도 부 릅 니 다.하프 만 나 무 는 모두 2 * n - 1 개의 결점 (성질) 이 있다.
2.      하프 만 트 리 구축: 값 이 가장 작은 두 개의 값 을 선택 하여 새 트 리 의 좌우 서브 트 리 로 하고 새 트 리 의 뿌리 결점 값 은 좌우 서브 트 리 뿌리 노드 의 값 의 합 이다.지난 두 그루 의 나 무 를 삭제 하고 새 나 무 를 숲 에 넣다.
 
 
2. 사고방식:
1. 하 브 만 트 리 의 구축: 입력 한 문자 와 가중치 에 따라 하 브 만 트 리 의 구축 과정 에 따라 먼저 N 개의 잎 결산 점 을 만 들 고 구축 과정 에서 부모 의 결산 점 을 만 들 며 좌우 아이의 결산 점 을 모두 0 으로 설정 한 다음 에 나머지 결산 점 (데 이 터 를 저장 하지 않 고 가중치 의 중간 결산 점 으로 만 한다) 을 구축한다.n 부터 2 * n - 1 까지 순환 하고 가중치 가 가장 작은 두 노드 를 선택 하여 부모 의 노드 위 치 를 순환 량 i 로 바 꾸 는 동시에 뿌리 노드 의 가중치 가 두 아이 만 과 좌우 아이 와 연결 되 는 것 으로 바 꿉 니 다.
2. 하 프 만 인 코딩: HC 2 차원 배열 의 지침 형식 으로 모든 문자 하 프 만 인 코딩 문자열 을 저장 합 니 다.왼쪽 아이 라면 0, 오른쪽 아 이 는 1 로 인 코딩 됩 니 다.판단 을 편리 하 게 하기 위해 fa 를 현재 노드 부모 노드 로 설정 합 니 다. 만약 에 HT [fa]. lch = = current 이면 배열 은 0, 반대로 1 을 저장 합 니 다. 저장 할 때 배열 은 높 은 아래 표지 판 에서 시작 하고 마지막 으로 다른 문자 배열 로 복사 하여 출력 하기에 편리 합 니 다.
3. 명문 을 암 문 (인 코딩) 으로 바 꾸 기: 한 줄 의 문 자 를 입력 하여 01010001 과 같은 형식의 암 문 으로 바 꿉 니 다.모든 문 자 를 이전에 저 장 된 HT 문자 배열 과 비교 할 것 입 니 다. 이때 HC [k] [] 에 해당 하 는 몇 개의 인 코딩 문자열 과 같 으 면 마지막 으로 비교 한 후에 얻 은 것 은 전체 인 코딩 문자열 입 니 다.
4. 암 문 을 명문 (디 코딩) 으로 바 꾸 기: 01010001... 형식의 암 문 을 입력 하여 의미 있 는 문자열 로 바 꿉 니 다. 뿌리 결산 점 에서 암 문 순 으로 하프 만 나 무 를 따라 아래로 내 려 가 고 0 이면 왼쪽 트 리 로 내 려 가 며 1 이면 오른쪽 트 리 로 갑 니 다. 결산 점 좌우 트 리 가 존재 하지 않 을 때 이때 의 문자 데 이 터 를 출력 하여 뿌리 노드 로 거 슬러 올 라 갑 니 다.
 
코드:

#include
#include
#include
#include
using namespace std;

typedef struct Node{
	int weight;  //   
	int parent;  //     ，0      
	int lch,rch; //        ，0      
	char data;
}HTNode ,*HuffmanTree;//               
typedef char **HuffmanCode;  //             
int n;           //         

int min(HuffmanTree HT,int k)
{
	int i=0;
	int min;//     weight   parent 0       
	int min_weight;//temp 
	while(HT[i].parent!=0) i++;
	min_weight=HT[i].weight;
	min=i;
	
	//  weight    parent 0    ，       min
	for(;i	fgets(datafile,255,fp1); cout<