C++實(shí)現(xiàn)哈夫曼樹的方法

更新時間：2020年04月28日 11:29:29 作者：李楊在路上

這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)哈夫曼樹的方法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下

序言

對于哈夫曼編碼，個人的淺薄理解就是在壓縮存儲空間用很大用處。
用一個很簡單例子，存儲一篇英文文章時候，可能A出現(xiàn)的概率較大，Z出現(xiàn)的記錄較小，如果正常存儲，可能A與Z存儲使用的空間一樣。但是用哈夫曼編碼方式，A經(jīng)常出現(xiàn)，所用編碼長度就短。

構(gòu)造哈夫曼樹，生成哈夫曼編碼

一、定義節(jié)點(diǎn)類型

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

二、定義樹類型（節(jié)點(diǎn)數(shù)組）

三要素：不定長數(shù)組，元素大小，有效元素個數(shù)

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

三、創(chuàng)建哈夫曼樹

1.將每一個節(jié)點(diǎn)都當(dāng)成一棵樹，初始化數(shù)組大小，并進(jìn)行賦值

RootA RA(4);
 //1.在RA.NodeA中存入字母和權(quán)值
 for (RA.n = 0;RA.n < RA.Size;RA.n++) {
 cout << "字母：";
 cin >> RA.NodeA[RA.n].C;
 cout << "權(quán)值：";
 cin >> RA.NodeA[RA.n].key;
 }

2.將樹按權(quán)值大小排序

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)遍歷數(shù)組，將RA.NodeA[0]和RA.Node[1]合并，其余向前移動，重新排序
(2)將RA.NodeA[0]，RA.NodeA[1]分別放在新合并的RA.NodeA[0]的左右子結(jié)點(diǎn)中

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.輸出哈夫曼編碼

遞歸，找到葉子節(jié)點(diǎn)，記錄路徑，左記錄0，右記錄1，直到輸出所有葉子節(jié)點(diǎn)

void CrateCode(Node *t,string &s) {
 //1.遍歷節(jié)點(diǎn)，遍歷左節(jié)點(diǎn)編碼為0,右節(jié)點(diǎn)則為1，遞歸，直到輸出所有葉子節(jié)
 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;
 }
}

以上是對構(gòu)造哈夫曼樹以及生成哈夫曼編碼的總結(jié)，希望對你們有所幫助！

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: