/*

　　例如，对于数列{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;

}

}

}