学习C++哈弗曼树

每次找出最小的俩顶点 构建一棵小树 再跟原来的树拼起来。就成了新的树。。直到只剩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>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个点 新建的顶点 填充信息	{		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)//左子			{				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;//都是同一个parent 权值等于他们的权值相加 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)//快速排序  本来以为排了序再一个一个加入好。。结果没啥用。可以不排序 {	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;	}}#endif //H_HPP
#include "h.hpp"int main(){	Do<int>d;	d.show();	system("pause");}