每次找出最小的倆頂點(diǎn) 構(gòu)建一棵小樹 再跟原來的樹拼起來。就成了新的樹。。直到只剩1個(gè)頂點(diǎn) 構(gòu)建成功

#ifndef H_HPP#define H_HPP#include <iostream>// 栗子 1 2 4 6        每?jī)蓚€(gè)頂點(diǎn) 都把權(quán)值相加合成一個(gè)新頂點(diǎn) 直到剩下一個(gè)點(diǎn) 就構(gòu)建完成這個(gè)哈夫曼樹了。 
//         //         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>class Do{PRivate:	Huf<T> *huff;	int *a;	int n;	int m;public:	Do();	~Do();	void Q_Sort(int a[],int l,int r);	void show();};template<typename T>Do<T>::Do(){	a = new int[5]{23, 43, 13, 11, 5 };	n = 5;	Q_Sort(a, 0, 4);	m = n * 2 - 1;	huff = new Huf<T>[m];	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; i++)	{		cout << a[i] << endl;		huff[i].w = a[i];	}		for (int i = 0; i < n - 1; i++)//n+i個(gè)點(diǎn) 新建的頂點(diǎn) 填充信息	{		int m1=9999999, m2=9999999, x1=0, x2=0;		for (int j = 0; j < n + i; j++)//在所有點(diǎn)中間 沒被使用過的點(diǎn) 選最小的		{			if (huff[j].w < m1&&huff[j].parent == -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;//都是同一個(gè)parent 權(quán)值等于他們的權(quán)值相加 x1 x2左右子		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)//快速排序  本來以為排了序再一個(gè)一個(gè)加入好。。結(jié)果沒啥用。可以不排序 {	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()//看所有頂點(diǎn)權(quán)值{	for (int i = 0; i < m; i++)	{		cout << i << " " << huff[i].w << endl;	}}#endif //H_HPP
#include "h.hpp"int main(){	Do<int>d;	d.show();	system("pause");}