溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要為大家展示了C++如何實現哈夫曼樹，內容簡而易懂，希望大家可以學習一下，學習完之后肯定會有收獲的，下面讓小編帶大家一起來看看吧。
序言
對于哈夫曼編碼，個人的淺薄理解就是在壓縮存儲空間用很大用處。
用一個很簡單例子，存儲一篇英文文章時候，可能A出現的概率較大，Z出現的記錄較小，如果正常存儲，可能A與Z存儲使用的空間一樣。但是用哈夫曼編碼方式，A經常出現，所用編碼長度就短。
構造哈夫曼樹，生成哈夫曼編碼
一、定義節點類型
struct Node {
char C;
long key;
Node *Left, *Right,*parent;
Node() { Left = Right = NULL; }
};二、定義樹類型（節點數組）
三要素：不定長數組，元素大小，有效元素個數
struct RootA {
Node *NodeA;
const int Size;
int n;
RootA(int Size) :Size(Size) { n = 0; NodeA = new Node[Size]; }
~RootA() { delete[]NodeA; }
};三、創建哈夫曼樹
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;
}
}以上就是關于C++如何實現哈夫曼樹的內容，如果你們有學習到知識或者技能，可以把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
