昨天 已經構建了哈弗曼樹了。哈夫曼編碼 就是從底倒著往前走 如果這點是左子 0右子1 直到根  而且每個編碼都不能是別的編碼的前綴

上完整馬 看注釋哈

#ifndef H_HPP#define H_HPP#include <iostream>//1 2 4 6 每兩個頂點 都把權值相加合成一個新頂點 直到剩下一個點 就構建完成這個哈夫曼樹了。 //         //         13                   //     6       7//       3       4//    1     2using namespace std;template<typename T>struct Huf{	int parent;	int lch;	int rch;	int w;	};template<typename T>struct HufCode{	int  bt[111];//這里就是放編碼的地方了 當前頂點為左子 0 右子 1	int  start;//開始位置	int  w;};template<typename T>class Do{PRivate:	Huf<T> *huff;	HufCode<T>*huffcode;	int *a;	int n;	int m;public:	Do();	~Do();	void Q_Sort(int a[],int l,int r);	void setCode();	void show();};template<typename T>Do<T>::Do(){	a = new int[5]{23, 43, 13, 11, 5 };	//這里可以有一個char b[] 里面放著·每個點的信息 a b c d  e 然后上面這些a[]存的是每個點的頻率	n = 5;	Q_Sort(a, 0, 4);	m = n * 2 - 1;	huff = new Huf<T>[m];	huffcode = new HufCode<T>[n];//初始化	for (int i = 0; i < m; i++)	{		huff[i].parent = -1;		huff[i].w = 0;		huff[i].lch = -1;		huff[i].rch = -1;	}			for (int i = 0; i < n - 1; i++)	{		int m1=9999999, m2=9999999, x1=0, x2=0;		for (int j = 0; j < n + i; j++)		{			if (huff[j].w < m1&&huff[j].parent == -1)//如果當前數比第一個數小 就替換第一個數 如果沒使用過 他的父節點才是-1 使用過就不能用了			{				m2 = m1;				m1 = huff[j].w;				x2 = x1;				x1 = j;			}			else if (huff[j].w<m2&&huff[j].parent==-1)//當前數比第二個數小			{				m2 = huff[j].w;				x2 = j;			}		}//這里已經找出來最小的倆頂點了
		huff[x1].parent = n + i;//就合并成新的樹		huff[x2].parent = n + i;		huff[n + i].w = huff[x1].w + huff[x2].w;		huff[n + i].lch = x1;		huff[n + i].rch = x2;	}}template<typename T>Do<T>::~Do(){	delete[]huff;	delete a;}template<>void Do<int>::Q_Sort(int a[], int l, int r){	int key = a[l];	int i = l;	int j = r;	if (i>=j)	{		return;	}	while (i < j)	{		while (i<j&&a[j]>key)			j--;		if (i < j)			a[i++] = a[j];		while (i<j&&a[i]<key)		{			i++;		}		if (i < j)			a[j--]= a[i];	}	a[i] = key;	Q_Sort(a, l, i - 1);	Q_Sort(a, i + 1, r);}template<typename T>void Do<T>::show()//看所有頂點權值{	for (int i = 0; i < m; i++)	{		cout << i << " " << huff[i].w << endl;	}	setCode();	for (int i = 0; i < n; i++)//訪問每個頂點	{				for (int j = huffcode[i].start+1 ; j < n; j++)//將huffcode[i]的編碼打印出來		{			cout << huffcode[i].bt[j];	        }		cout << endl;	}}template<typename T>void Do<T>::setCode(){		HufCode<T>*tempCode = new HufCode<T>;	for (int i = 0; i < n; i++)	{		tempCode->start = n - 1;//先從底部開始倒著走				tempCode->w = huff[i].w;		int child = i;//當前點作為孩子		int parent = huff[i].parent;//設置好父節點
			while (parent != -1)//父節點不為空就一直向上找			{				if (child == huff[parent].lch)//左 0					tempCode->bt[tempCode->start] = 0;				else					tempCode->bt[tempCode->start] = 1;				tempCode->start--;       // 假設最后那個是1 就變為00001 然后start-- 下一次還是1 就 00011了			child=parent;//往上走 父變子 找父的父作為新的parent			parent = huff[child].parent;			}			for (int j = n - 1; j > tempCode->start;j--)		{			huffcode[i].bt[j] = tempCode->bt[j];//找完了i這個頂點的全部父了 就把編碼裝進huffcode[i]的bt					}		cout << endl;			huffcode[i].start = tempCode->start;//編碼開始位置			huffcode[i].w = tempCode->w;//權值也存好			}	delete tempCode;}#endif //H_HPP
#include "h.hpp"int main(){	Do<int>d;	d.show();	system("pause");}嗯。醬紫。