目錄

哈夫曼編碼（最優二叉樹）

一、優勢：縮短電文長度

二、思想：

三、過程：?

四、圖解實現過程：?

五、總代碼?

---

哈夫曼編碼（最優二叉樹）

一、優勢：縮短電文長度

?二、思想：

????????獲取每個字符出現的頻率，用一個大小為[256]的數組保存（因為ASCII碼是256個），最后作為每個字符的權重。權重越大，意味著出現頻率越大，希望它的碼長越短，這樣總體電文最小。最后把這些字符（不重復部分）、權重依次放入結點中，把這些結點作為一個個元素，從小到大依次組成哈夫曼樹。

三、過程：?

先統計出字符出現的頻率，作為其權重。
編碼保存：把每個不重復的字符頻率作為權重，用二叉樹進行排序，二叉樹上面的字符權重大(出現頻率高)，編碼的碼長短，下面的字符權重小(出現頻率低)，編碼碼長長。
編碼：輸入字符，遍歷整個二叉樹，對比是否和葉子結點相同，是則保存編碼。（左0右1）
譯碼：輸入二進制碼，在二叉樹中走一遍，走到葉子結點即為需要保存的編碼。（左0右1）

（向左走為0，向右走為1）

四、圖解實現過程：?

五、總代碼?

//哈夫曼編碼
//優勢：縮短電文長度
//先統計出字符出現的頻率，作為其權重。
//編碼保存：把每個不重復的字符作為權重，用二叉樹進行排序，二叉樹上面的字符權重高(出現頻率高)，編碼的碼長短，
//下面的字符權重小(出現頻率低)，編碼碼長長
//編碼：輸入字符，遍歷整個二叉樹，對比是否和葉子結點相同，是則保存編碼
//譯碼：輸入二進制碼，在二叉樹中走一遍，走到葉子結點即為需要保存的編碼。
#include<iostream>
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
using namespace std;#define MAXSIZE 100char str[MAXSIZE];						//要編碼保存的電文
char str_en[MAXSIZE];					//編碼時輸入的電文
char str_de[MAXSIZE];					//解碼時輸出的電文
int code_de[MAXSIZE];				//解碼時存儲
int frequency[256] = { 0 };			//統計各字符出現頻率
int flag_c[256] = { 0 };					//只存儲一次，判斷是否第一次出現
int length = 0;								//數組總長度
int LENGTH = 0;							//葉子結點長度
int sumFrequency = 0;					//權重之和
int index_s = 0;							//字符串數組
int code[64];								//編碼
int index_c = -1;							//編碼數組
int step = 0;									//編碼/譯碼步數（從哈夫曼樹的根往后下走）
int sumCode[4 * MAXSIZE];			//總編碼
int flag_exit = 0;							//退出符號
int index = 0;								//譯碼數組
int decode_length;						//譯碼數組長度//樹元素
typedef struct Tnode
{char data;									//存放數據int frequency;							//權重(出現的頻率）struct Tnode* lchild, * rchild;	//左右孩子int code[64];							//每個字符的哈夫曼碼int code_length;						//編碼長度
}Tnode;
Tnode T[MAXSIZE];						//存放各結點
Tnode* hfmTree;							//哈夫曼根結點
Tnode* Pre;									//存放前一個結點//輸入字符串
void Input()
{cout << "請輸入需要編碼并保存編碼的電文：\n";gets_s(str, 100);
}//輸入待編碼數組
void Encode_Input()
{cout << "請輸入需要編碼的電文：\n";getchar();gets_s(str_en, MAXSIZE);
}//輸出編碼后的數組
void Encode_Output()
{int i = 0;//下標for (i = 0; i <= index_c; i++){cout << sumCode[i];}cout << endl;
}//輸入待譯碼數組
void Decode_Input()
{int i = 0;char ch = ' ';step = 0;cout << "請輸入需要譯碼的二進制碼：\n";index = 0;getchar();									//吸收空格//讀取每位字符，挨個化整存入整形數組while (ch != '\n')						//把每位字符保存到數組（換行退出）{ch = getchar();						//讀取一位字符if (ch != '\n')code_de[i++] = ch - 48;	//字符化整}decode_length = i;					//譯碼數組長度
}//獲取權重
void GetFrequency()
{int i = 0;//統計字符頻率for (i = 0; i < strlen(str); i++){frequency[str[i]]++;					//頻率表中對應字符出現數值+1}
}//創建樹節點
void CreateTnode()
{int i = 0, count = 0;//添加字符和頻率到樹結構體數組中for (i = 0; i < strlen(str); i++){if (flag_c[str[i]] == 0)				//首次出現{flag_c[str[i]] = 1;					//標志出現過T[count].data = str[i];T[count].frequency = frequency[str[i]];T[count].lchild = NULL;T[count].rchild = NULL;sumFrequency += T[count].frequency;		//計算葉子結點總權重count++;}}LENGTH = count;length = count;
}//獲取最小值						/***********注：要整體替換，否則后面會出現混亂**********/
Tnode Getmin()
{int i, j, max = 0;Tnode temp;//選擇排序(權重從高到低)（最后的一個最小）for (i = 0; i < length; i++){max = i;for (j = i; j < length; j++){if (T[j].frequency > T[max].frequency)max = j;}if (max != i){temp = T[i];								//整體替換T[i] = T[max];T[max] = temp;}}return T[--length];			//取出最后一個結點（最小權重）
}//遍歷
void Traverse(Tnode* N)
{int i = 0;if (N != NULL){Traverse(N->lchild);if (N->lchild == NULL && N->rchild == NULL)					//葉子結點{printf("%c結點權值：%d\t編碼：", N->data, N->frequency);for (i = 0; i < N->code_length; i++){cout << N->code[i];}cout << endl;}Traverse(N->rchild);}
}//初始化哈夫曼樹
void Init_hfmTree()
{hfmTree = (Tnode*)malloc(sizeof(Tnode));			//創建哈夫曼樹hfmTree->lchild = NULL;hfmTree->rchild = NULL;Pre = hfmTree;														//前一個結點
}//創建哈夫曼樹
Tnode Create_hfmTree()
{int len;Tnode* N = (Tnode*)malloc(sizeof(Tnode));while (N->frequency != sumFrequency){N = (Tnode*)malloc(sizeof(Tnode));N->lchild = (Tnode*)malloc(sizeof(Tnode));			//左孩子N->rchild = (Tnode*)malloc(sizeof(Tnode));			//右孩子if (length != -1)*N->lchild = Getmin();elseN->lchild = NULL;												//地址設為空if (length != -1)*N->rchild = Getmin();elseN->rchild = NULL;												//地址設為空N->data = '#';															//表示空N->frequency = N->lchild->frequency + N->rchild->frequency;		//求權重之和T[length++] = *N;													//放入數組}return *N;
}//結點編碼（初始存檔編碼）
void NodeEncode(Tnode* N)
{int i = 0;if (N != NULL){//向左走if (Pre->lchild == N){code[step++] = 0;				//向左走}else if (Pre->rchild == N){code[step++] = 1;				//向右走}Pre = N;									//保存上一結點if (N->lchild != NULL && N->rchild != NULL)		//未到達葉子結點{NodeEncode(N->lchild);step--;										//向回走Pre = N;									//保存上一結點NodeEncode(N->rchild);step--;										//向回走}else												//到達葉子結點{for (i = 0; i < step; i++)N->code[i] = code[i];			//記錄編碼N->code_length = step;			//記錄碼長}}
}//編碼
void Encode(Tnode* N)
{int i = 0;if (flag_exit)return;if (N != NULL && str[index_s] != '\0')				//到達葉子結點或者字符串到尾{if (N->lchild != NULL && N->rchild != NULL)		//未到達葉子結點{Encode(N->lchild);Encode(N->rchild);}else														//找到葉子結點{if (N->data == str_en[index_s])		//是要找的葉子結點{flag_exit = 1;							//退出標志for (i = 0; i < N->code_length; i++){sumCode[++index_c] = N->code[i];			//編碼存入}}}}
}//譯碼
void Decode(Tnode* N)
{int i = 0;if (N != NULL){if (N->lchild != NULL || N->rchild != NULL)					//沒有查找到葉子結點{if (code_de[index] == 0)			//向左走{index++;step++;Decode(N->lchild);step--;							//彈出來}else if (code_de[index] == 1)	//向右走{index++;step++;Decode(N->rchild);step--;							//彈出來}}else					//查找到葉子結點{cout << N->data;			//輸出譯碼結果}}
}int main()
{int choice;int i;Input();						//輸入字符GetFrequency();		//獲取字符串//葉子結點的創建與排序CreateTnode();			//創建樹節點//哈夫曼樹的初始化與創建Init_hfmTree();*hfmTree = Create_hfmTree();//結點編碼step = 0;NodeEncode(hfmTree);while (1){system("cls");cout << "請選擇需要的服務：\n";cout << "1、查找所有已保存的結點編碼和權\n";cout << "2、整體編碼\n";cout << "3、整體譯碼\n";cout << "0、退出\n";cout << "請選擇您需要的服務：\n";cin >> choice;//選項switch (choice){//0、退出case 0:exit(0);break;//1、遍歷所有葉子結點case 1:Traverse(hfmTree);				//查找所有編碼和權break;case 2:index_s = 0;Encode_Input();					//編碼輸入//逐字符編碼while (str_en[index_s] != '\0'){flag_exit = 0;Encode(hfmTree);index_s++;}Encode_Output();					//編碼輸出break;//3、譯碼case 3://輸入譯碼數組Decode_Input();index = 0;while (index < decode_length){//譯碼step = 0;Decode(hfmTree);			//譯碼并輸出}cout << endl;break;default:cout << "無此選項！" << endl;break;}system("pause");}return 0;
}

總結

以上是生活随笔為你收集整理的数据结构与算法（6-5）二叉树的应用--哈夫曼树与哈夫曼编码的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。