什么是哈夫曼树

哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1L1+W2L2+W3L3+…+ WnLn)，N个权值Wi(i=1,2,…n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,…n)。可以证明哈夫曼树的WPL是最小的。 构造哈夫曼树的算法如下： 1）对给定的n个权值{W1,W2,W3,…,Wi,…,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,…,Ti,…, Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。 2）在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。 3）从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。 4）重复2）和3），直到集合F中只有一棵二叉树为止。

    例如，对于4个权值为1、3、5、7的节点构造一棵哈夫曼树，其构造过程如下图所示：

哈夫曼树的算法实现

#include<iostream>
#include<iomanip>
#include<cfloat>
using namespace std;
const int n=5;
const int m=2*n-1;
typedef struct{
    float weight;
    int parent,lchild,rchild;
}nodetype;
typedef nodetype hftree[m];
hftree T;

void huffman(hftree T){
    int p1,p2,i,j;
    float small1,small2;
    for(i=0;i<n;i++){
        T[i].parent=T[i].lchild=T[i].rchild=-1;
    }
    for(i=0;i<n;i++){
        cin>>T[i].weight;
    }
    for(i=n;i<m;i++){
        p1=p2=-1;
        small1=small2=FLT_MAX;
        for(j=0;j<=i-1;j++){
            if(T[j].parent!=-1)continue;
        	if(T[j].weight<small1){
				small2=small1;
				small1=T[j].weight;
				p2=p1;
				p1=j;
			}
			else if(T[j].weight<small2){
				small2=T[j].weight;
				p2=j;
			}
        }
        T[p1].parent=T[p2].parent=i;
        T[i].parent=-1;
        T[i].lchild=p1;
        T[i].rchild=p2;
        T[i].weight=small1+small2;
    }
}

输出哈夫曼树

这里用到了头文件，主要是运用setw()控制一下输出的格式

void print_tree(hftree T){
    for (int i = 0; i < m; i++) {
		cout << "index weight parent left right" << endl;;
		cout << left;
		cout <<setw(5)<< i << " ";
		cout << setw(6) << T[i].weight << " ";
		cout << setw(6) << T[i].parent << " ";
		cout << setw(6) << T[i].left << " ";
		cout << setw(6) << T[i].right << endl;
	}
}