C++하프 만 트 리 를 실현 하 는 방법

서언
하 프 만 인 코딩 에 대해 개인의 얕 은 이 해 는 저장 공간 을 압축 하 는 데 큰 도움 이 된다 는 것 이다.
아주 간단 한 예 를 들 어 영어 문장 한 편 을 저장 할 때 A 가 나타 날 확률 이 높 고 Z 가 나타 날 기록 이 적 으 며 정상적으로 저장 하면 A 가 Z 저장 소 에서 사용 하 는 공간 과 같 을 수 있다.그러나 하프 만 인 코딩 방식 으로 A 가 자주 나타 나 고 인 코딩 길이 가 짧다.
하프 만 트 리 를 구성 하여 하프 만 인 코딩 생 성
노드 종류 정의

struct Node {
 char C;
 long key;
 Node *Left, *Right,*parent;
 Node() { Left = Right = NULL; }
};

2.트 리 형식 정의(노드 배열)
세 가지 요소:부정 장수 그룹,원소 크기,유효 원소 개수

struct RootA {
 Node *NodeA;
 const int Size;
 int n;
 RootA(int Size) :Size(Size) { n = 0; NodeA = new Node[Size]; }
 ~RootA() { delete[]NodeA; }
};

3.하프 만 트 리 만 들 기
1.모든 노드 를 하나의 나무 로 생각 하고 배열 크기 를 초기 화하 고 값 을 부여 합 니 다.

RootA RA(4);
 //1. RA.NodeA        
 for (RA.n = 0;RA.n < RA.Size;RA.n++) {
 cout << "  ：";
 cin >> RA.NodeA[RA.n].C;
 cout << "  ：";
 cin >> RA.NodeA[RA.n].key;
 }

2.트 리 를 가중치 크기 로 정렬

void Sort(RootA *ra) {
 for (int i = 0;i < ra->n;i++) {
 bool ESC = false;
 for (int j = 0;j < ra->n - i - 1;j++) {
  if (ra->NodeA[j].key > ra->NodeA[j + 1].key) {
  Node T;T = ra->NodeA[j];ra->NodeA[j] = ra->NodeA[j + 1];ra->NodeA[j + 1] = T;
  ESC = true;
  }
 }
 if (!ESC) return;
 }
}

3.(1)배열 을 옮 겨 다 니 며 RA.NodeA[0]와 RA.Node[1]를 합 쳐 나머지 는 앞으로 이동 하여 정렬 합 니 다.
(2)RA.NodeA[0],RA.NodeA[1]를 새로 합 병 된 RA.NodeA[0]의 왼쪽 오른쪽 자 결점 에 각각 넣는다.

while (RA.n > 1) {
 //1. RA.NodeA[0] RA.NodeA[1]  ，       
 Node *NewNode0 = new Node;
 *NewNode0 = RA.NodeA[0];
 Node *NewNode1 = new Node;
 *NewNode1 = RA.NodeA[1];
 RA.NodeA[0].C = ' ';
 RA.NodeA[0].key = RA.NodeA[0].key + RA.NodeA[1].key;
 RA.NodeA[0].Left = NewNode0;
 NewNode0->parent = &RA.NodeA[0];
 RA.NodeA[0].Right = NewNode1;
 NewNode1->parent = &RA.NodeA[0];
 for (int i = 1;i < RA.n-1;i++) {
  RA.NodeA[i] = RA.NodeA[i + 1];
 }
 RA.n = RA.n - 1;
 //2.  
 Sort(&RA);
 }

4.하프 만 인 코딩 출력
재 귀,잎 노드 를 찾 고 경 로 를 기록 하 며 왼쪽 기록 0,오른쪽 기록 1,모든 잎 노드 를 출력 할 때 까지

void CrateCode(Node *t,string &s) {
 //1.    ，        0,     1，  ，         
 if (t->Left != NULL && t->Right != NULL) {
 s.push_back('0'); CrateCode(t->Left, s);
 s.pop_back();
 s.push_back('1');CrateCode(t->Right, s);
 s.pop_back();
 }
 else {
 cout << "     ：";
 cout << t->C << ":" << s<<endl;
 }
}

이상 은 하프 만 트 리 를 구성 하고 하프 만 인 코딩 을 생 성 하 는 데 도움 이 되 기 를 바 랍 니 다!
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.