哈夫曼树时数据结构中树这一部分比较重要的知识点，把学校放在mooc上的这一部分教学视频看了几遍，终于动手实现了。其实也不是很难，但我还是搞了老半天，才将代码中的bug修复，觉得操作的数据有点多，弄不好就乱了！！！
哈夫曼树又称最优二叉树，给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
哈夫曼树的数据结构：
我使用的时静态链表来存储整个树的节点，刚开始给叶子节点的权值，将叶子节点加入到哈夫曼树的静态链表中，并将其父亲，左孩子，有孩子置为0，接下来就是在这几个叶子节点中找权值最小的两个叶子节点，将权值求和作为这两个子节点的父节点权值，将这两个孩子节点的标志位置为1，将父节点的标志位置为0。将父节点的左右孩子置为那两个最小权值节点的下标，将那两个最小权值节点的父亲下标置为相应父亲节点的下标。之后以此类推…
看代码吧！！！就我这表达能力讲是不可能讲清楚了！！！
c++实现的哈夫曼树，挺方便的语言，但就是语法有点怪异！！！让人捉摸不透！最近学了这门语言，就用上了！本来觉得用set容器可以更加简单，因为set容器在存的时候就将元素排序了！但在最后发现没有把它这一点又是体现出来！
#include<algorithm>
#include<set>
#include<iterator>
#include<iostream>
#include<vector>
#include<string.h>
#include<stdio.h>
using namespace std;
//创建hafu曼树
class hafu{
private:
int weight ;
int tag ;
int l,r,p ;
public:
hafu(){}
~hafu(){}
//在主函数里面要存的是多个对象，我将权值等数据设置成了私有属性，所以就定义了静态方法
static void init(set<int>arr,hafu tree[]);
static void getHafu(set<int>arr,hafu tree[]);
static void getNode(int j,hafu tree[] ,int s1 ,int s2);
static void print(int size,hafu tree[]);
static int getmax(int j ,hafu tree[]);
};
//获取当前hafu曼树中权值最大值
int hafu::getmax(int j , hafu tree[]){
int i ;
int max = -1 ;
for(i = 0 ;i< j ;i ++){
if(max < tree[i].weight ){
max = tree[i].weight ;
}
}
return max ;
}
//打印创建好的hafu曼树好的
void hafu::print(int size ,hafu tree[]){
int i;
for(i = 0 ;i < size-1;i++){
cout<<tree[i].weight<<" "<<tree[i].p<<" "<<tree[i].l<<" "<<tree[i].r<<endl;
}
}
//将set容器中的权值存到树中，并将其他节点数据权值0
void hafu::init(set<int>arr,hafu tree[]){
int i = 0 ;
//定义构造器
set<int>::iterator iter ;
iter = arr.begin();
//将哈夫曼树中的当前节点的孩子父母置为零
for(i = 0 ; i < arr.size();i++){
tree[i].weight = *iter;
if(iter==arr.end())break ;
tree[i].l = 0;
tree[i].p = 0 ;
tree[i].r = 0 ;
tree[i].tag = 0;
iter++ ;
}
}
void hafu::getHafu(set<int>arr,hafu tree[]){
int a = arr.size() ;
int j =0;
int s1 ,s2 ;
for(j = arr.size() ; j< 2*a-1 ;j++){
//获取从0～j的序列中没有父节点的两个权值最小的叶子节点，将其在树中所处的下标返回
getNode(j ,tree,s1,s2);
//最终结束的临界点是只有一个最小节点返回，另一个是无效的节点
//这个节点其实是整棵树中权值最大的节点
if(s1!=-1&&s2==-1){
tree[j].weight = tree[s1].weight ;
break;
}
//将两个最小权值的和作为父节点的权值，将父节点的标志位置为0
tree[j].weight = tree[s1].weight+tree[s2].weight ;
//左右孩子下标为返回的两个下标，并将两个节点的标志位置为1
//表示已经有节点了，下次找权值最小的两个叶子时就直接跳过这两个节点(人家已经有父亲了，不再需要父亲啦)
tree[j].l = s1;
tree[j].r = s2;
tree[s2].tag = 1 ;
tree[j].tag= 0;
tree[s2].p = j ;
tree[s1].p = j ;
}
}
//获取两个权值最小的叶子节点
void hafu::getNode(int j ,hafu tree[],int & s1 ,int& s2){
int i= 0 ;
int k= 0;
int temp = -1 ,temp1 =-1 ;
//最开始将两个值置为树中权值最大的，然后遇到满足条件的小权值节点就记录下标
s1 = getmax(j,tree)+1;
s2 = s1+1;
int t = s2 ;
for(i = 0 ; i < 2 ; i++){
for(k = 0; k< j ; k++){
//和冒泡排序思想比较像，在树中先找第一个权值最小节点
//该结点满足：
//没有父亲节点(标志位不为1)并且比当前记录的最小权值要小
//找到的话就记录在树中所处下标
if(i== 0&&tree[k].tag ==0&&s1>tree[k].weight){
s1 = tree[k].weight;
temp = k ;
}
//找第二个最小权值的节点
if(i ==1&&tree[k].tag ==0&&s2>tree[k].weight){
s2= tree[k].weight;
temp1= k ;
}
}
//第一轮找完将将第一轮找的节点标志位改为1，他可能是即将右父亲的孩子
tree[temp].tag = 1;
}
//将两个最小权值下标传给s1,s2
s2 = temp1 ;
s1 = temp ;
}
int main(){
set<int>arr ;
int a ;
cout<<"Input data:(-1 to end)"<<endl;
while(cin>>a){
if(a== -1)break ;
arr.insert(a);
}
set<int>::iterator iter = arr.begin();
getchar();
int s =arr.size();
s= 2*s;
hafu *tree= new hafu[s];
int j = 0;
//将新申请的空间全部置为零
for(j =0 ; j< s;j++){
bzero(&tree[j],sizeof(tree[j]));
}
hafu::init(arr,tree);
hafu::getHafu(arr,tree);
hafu::print(s,tree);
}
运行截图：
分别打印权值，父节点，右孩子节点，左孩子节点
哈夫曼树总结至此！最后留个问题，很明显上面的程序没有释放内存，该如何将new的内存时释放呢？我用delete tree 或者循环好像行不通？