夕拾算法进阶篇：26)哈夫曼树及其编码

给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

如果仅仅只是为了求最小带权路径长度，只要掌握哈夫曼树的构建思想，反复选择 两个最小的元素，合并，直到剩下一个元素。

基于这个思想，可以先使用一个数组保存树的所有节点，然后不断选择最小的两个节点并把其中一个的值设置为二者的和，另一个节点删除(NULL)。然后重复该操作n-1(n为结点个数)次就可以构建出哈夫曼树了，其实现代码如下：

#include <iostream>using namespace std;const int M=100;const int Inf=0x7fffffff;bool code[M];//保存01编码 int ans=0; //保存最小带权路径长度 //树结构定义 struct Node{	int weight; //输入字符的权重 	char ch; //保存输入的字符 	Node *lchild,*rchild; 	 }; //简单封装下新建节点的操作 Node* newNode(int w,char c){	Node* n=new Node();	n->weight=w;	n->ch=c;	n->lchild=n->rchild=NULL; }//遍历哈夫曼树  cue=当前的数的层次 tag=左右边标记01 void travel(Node *root,int cur,bool tag){	if(root){		code[cur]=tag; //标记边 		if(!root->lchild&&!root->rchild){			ans+=root->weight*cur; //累加最小带权路径长度 			cout<<root->ch<<":"; 			for(int i=1;i<=cur;i++){				cout<<code[i]<<" "; //打印编码 			}			cout<<endl;		}		travel(root->lchild,cur+1,0);		travel(root->rchild,cur+1,1);	}} //构建哈夫曼树 Node* createTree(Node **rs,int n){	int i,m1,m2,n1=n; //m1/m2保存rs最小和次小结点的下标 	Node *root; //根节点 	while(--n1){ //进行n-1次合并后只剩下一个根结点 		Node *min1=newNode(Inf,0),*min2=newNode(Inf,0); //保存小和次小结点		for(i=0;i<n;i++){			if(rs[i]&& min1->weight > rs[i]->weight){				min1=rs[i]; m1=i; //获得最小的结点和下标 			}		}			rs[m1]=NULL; //在rs数组中伪删掉最小的结点 		for(i=0;i<n;i++){			if(rs[i]&& min2->weight > rs[i]->weight){				min2=rs[i];	m2=i;			}		}		root=new Node(); //构建新root节点，其左右子树是最小和次小结点		root->weight=min1->weight+min2->weight;		root->lchild=min1; 		root->rchild=min2;		rs[m2]=root; //把rs的次小结点更新为当前新root结点 	}	return root; //返回最终的root结点 } int main(){	int w,n,i,m1,m2;	Node **rs=new Node*[M];//初始所有节点都是单独的root 	cin>>n;	char ch[M];	for(i=0;i<n;i++){		cin>>ch[i];	}	for(i=0;i<n;i++){		cin>>w;		rs[i]=newNode(w,ch[i]);	}	Node *root=createTree(rs,n);	travel(root,0,0);	cout<<ans<<endl; } /* 5-表示字符的个数，接下2行为字符和对应出现的权值 5A B C D E 1 3 4 2 5*/