HuffmanTree

/* 

   

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

   }

   }

}