ハフマンツリーとハフマン符号化

#include <iostream>

#include <string.h>

using namespace std;

#define N 1000

struct HufmTree// 

{

  char ch;// 

  int weight;// 

  int parent,lchild,rchild;

};

struct HuffmanCode

{

    char ch;

    char bits[N+1];

};

HufmTree tree[N];// 

HuffmanCode h[N];// 

void select(HufmTree tree[],int n,int&min1,int &min2)

// parent  0 

{

    int mw1=100000,mw2=100000;

    for(int i=1;i<=n;i++)

    {

       if(tree[i].parent!=0)continue;

        if(tree[i].weight<=mw1)

       {

           mw2=mw1;

           mw1=tree[i].weight;

           min2=min1;

           min1=i;

       }

       else if(tree[i].weight<mw2)

       {

           mw2=tree[i].weight;

           min2=i;

        }

    }

 

}

void CreatHuffman(HufmTree *tree,int n)//n 

{

   if(n<=1)return;

    int m=2*n;

   for(int i =1;i<m;i++)// 

    {

       tree[i].parent=0;

       tree[i].lchild=0;

       tree[i].rchild=0;

       tree[i].weight=0;

    }

   for(int i=1;i<=n;i++)// 

    {

       cin>>tree[i].ch;

       cin>>tree[i].weight;

    }

   for(int i=n+1;i<m;i++)

    {

       int min1,min2;//min1,min2， 

        select(tree,i-1,min1,min2);

       tree[min1].parent=i;tree[min2].parent=i;

       tree[i].lchild=min1;tree[i].rchild=min2;

       tree[i].weight= tree[min1].weight + tree[min2].weight ;

    }

}

void HuffmanCoding(HufmTree *tree,HuffmanCode*h,int n)//n 

{

    int c,p;

    int start;

    char cd[n+1];

    cd[n]='\0';

    for(int i=1;i<=n;i++)

    {

       h[i].ch=tree[i].ch;

       start = n;

       c=i;

       p=tree[c].parent;

       while(p==tree[c].parent)

       {

           if(tree[p].lchild==c)//  tree[c] tree[p] ， ‘0’

                cd[--start]='0';

            else

                cd[--start]='1';

           c=p;

           if(p==2*n-1)break;

           else p=tree[p].parent;

       }

       for(int j=start;j<=n;j++)

       {

           h[i].bits[j-start]=cd[j];

       }

    }

}