例如，对于数列{pi}={5, 3, 8, 2, 9}，Huffman树的构造过程如下：
1. 找到{5, 3, 8, 2, 9}中最小的两个数，分别是2和3，从{pi}中删除它们并将和5加入，得到{5, 8, 9, 5}，费用为5。
2. 找到{5, 8, 9, 5}中最小的两个数，分别是5和5，从{pi}中删除它们并将和10加入，得到{8, 9, 10}，费用为10。
3. 找到{8, 9, 10}中最小的两个数，分别是8和9，从{pi}中删除它们并将和17加入，得到{10, 17}，费用为17。
4. 找到{10, 17}中最小的两个数，分别是10和17，从{pi}中删除它们并将和27加入，得到{27}，费用为27。
5. 现在，数列中只剩下一个数27，构造过程结束，总费用为5+10+17+27=59。
*/ #include <stdlib.h> #include <iostream> using namespace std; typedef struct node{ struct node *left; struct node *right; int weight; char data; }Huff; class Huffm{ private: Huff **F; int n; Huff *root; public: Huffm(int *pi,int n){ Huff *p=NULL; F=(Huff **)malloc(sizeof(Huff *)); for(int i=0;i < n ;i++){ p=(Huff *)malloc(sizeof(Huff)); p->left=p->right=NULL; p->weight=pi[i]; p->data='a'+i; F[i]=p; }//for this->n=n; } void BuiltHuff();//建树 Huff *gettree();//返回头结点 void Printree(Huff *tree);//层遍历输出整棵树 }; int main(void) { int pi[]={5,3,8,2,9}; Huffm *tree=new Huffm(pi,5); tree->BuiltHuff(); Huff *root=tree->gettree(); tree->Printree(root); return 0; } void Huffm::BuiltHuff() { Huff *p=NULL; int k1,k2; for(int i=0;i<n-1;i++){ //最小次小 for(k1=0;!F[k1];k1++); for(k2=k1+1;!F[k2];k2++); for(int j=k2;j<n;j++){ if(F[j]){ if(F[j]->weight<F[k1]->weight){ k2=k1; k1=j; }else if(F[j]->weight<F[k2]->weight){ k2=j; } }/*if F[j] */ }/*for j*/ //建树 p=(Huff *)malloc(sizeof(Huff)); p->data=0; p->left=F[k1]; p->right=F[k2]; p->weight=F[k1]->weight+F[k2]->weight; F[k1]=p; F[k2]=NULL; }/*for i*/ this->root=F[k1]; } Huff *Huffm::gettree()//返回头结点 { return root; } void Huffm::Printree(Huff *tree)//层遍历输出整棵树 { Huff **p=(Huff **)malloc(sizeof(Huff *)); Huff *pnode=NULL; int head=0,tail=0; p[++tail]=tree; while(tail!=head){ head=(head+1)%5; cout<<p[head]->weight<<p[head]->data<<" "; pnode=p[head]; if(pnode->left){ tail=(tail+1)%5; p[tail]=pnode->left; } if(pnode->right){ tail=(tail+1)%5; p[tail]=pnode->right; } } }
