給定n個權(quán)值作為n個葉子結(jié)點，構(gòu)造一棵二叉樹，若帶權(quán)路徑長度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)值較大的結(jié)點離根較近。

如果僅僅只是為了求最小帶權(quán)路徑長度，只要掌握哈夫曼樹的構(gòu)建思想，反復(fù)選擇 兩個最小的元素，合并，直到剩下一個元素。

基于這個思想，可以先使用一個數(shù)組保存樹的所有節(jié)點，然后不斷選擇最小的兩個節(jié)點并把其中一個的值設(shè)置為二者的和，另一個節(jié)點刪除(NULL)。然后重復(fù)該操作n-1(n為結(jié)點個數(shù))次就可以構(gòu)建出哈夫曼樹了，其實現(xiàn)代碼如下：

#include <iostream>using namespace std;const int M=100;const int Inf=0x7fffffff;bool code[M];//保存01編碼 int ans=0; //保存最小帶權(quán)路徑長度 //樹結(jié)構(gòu)定義 struct Node{	int weight; //輸入字符的權(quán)重 	char ch; //保存輸入的字符 	Node *lchild,*rchild; 	 }; //簡單封裝下新建節(jié)點的操作 Node* newNode(int w,char c){	Node* n=new Node();	n->weight=w;	n->ch=c;	n->lchild=n->rchild=NULL; }//遍歷哈夫曼樹  cue=當(dāng)前的數(shù)的層次 tag=左右邊標(biāo)記01 void travel(Node *root,int cur,bool tag){	if(root){		code[cur]=tag; //標(biāo)記邊 		if(!root->lchild&&!root->rchild){			ans+=root->weight*cur; //累加最小帶權(quán)路徑長度 			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);	}} //構(gòu)建哈夫曼樹 Node* createTree(Node **rs,int n){	int i,m1,m2,n1=n; //m1/m2保存rs最小和次小結(jié)點的下標(biāo) 	Node *root; //根節(jié)點 	while(--n1){ //進(jìn)行n-1次合并后只剩下一個根結(jié)點 		Node *min1=newNode(Inf,0),*min2=newNode(Inf,0); //保存小和次小結(jié)點		for(i=0;i<n;i++){			if(rs[i]&& min1->weight > rs[i]->weight){				min1=rs[i]; m1=i; //獲得最小的結(jié)點和下標(biāo) 			}		}			rs[m1]=NULL; //在rs數(shù)組中偽刪掉最小的結(jié)點 		for(i=0;i<n;i++){			if(rs[i]&& min2->weight > rs[i]->weight){				min2=rs[i];	m2=i;			}		}		root=new Node(); //構(gòu)建新root節(jié)點，其左右子樹是最小和次小結(jié)點		root->weight=min1->weight+min2->weight;		root->lchild=min1; 		root->rchild=min2;		rs[m2]=root; //把rs的次小結(jié)點更新為當(dāng)前新root結(jié)點 	}	return root; //返回最終的root結(jié)點 } int main(){	int w,n,i,m1,m2;	Node **rs=new Node*[M];//初始所有節(jié)點都是單獨的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-表示字符的個數(shù)，接下2行為字符和對應(yīng)出現(xiàn)的權(quán)值 5A B C D E 1 3 4 2 5*/