//Huffman.cpp
//赫夫曼樹與赫夫曼編碼
#include<iostream.h>
#include<iomanip.h>
const int MaxV=1000;//初始設定的最大權值
const int MaxBit=10;//初始設定的最大編碼位數
const int MaxN=10;//初始設定的最大結點數
//赫夫曼樹的結點結構
typedef struct
  {int weight;//權值
   int flag;  //標記
   int parent;//雙親結點下標
   int left;//左孩子下標
   int right;//右孩子下標
  }HuffNode;
  typedef struct
  {int bit[MaxN];//存放編碼數組
   int start;//編碼的起始下標
   int weight;//字符的權值
  }Code;
//類定義
class HuffmanT
{public:
  //構造函數
  HuffmanT(HuffNode *&,Code *&,int);
  //創建葉結點個數為n,權值數組為weight的赫夫曼樹HuffTree
  void MakeHufm(int weight[],int n);
  //由n個結點的赫夫曼樹HuffTree構造赫夫曼編碼huffCode
  void HuffCode(int n);
 private:
  HuffNode *HuffTree;
  Code *huffCode;
};
HuffmanT::HuffmanT(HuffNode *&huffnode,Code *&huCode,int n)
{huffnode=new HuffNode[2*n+1];
 huCode=new Code[n];
 HuffTree=huffnode;
 huffCode=huCode;
}
void HuffmanT::MakeHufm(int weight[],int n)
{int j,m1,m2,x1,x2,i;
 //赫夫曼樹HuffTree的初始化
 for(i=0;i<2*n-1;i++)
 {if(i<n) HuffTree[i].weight=weight[i];
  else HuffTree[i].weight=0;
  HuffTree[i].parent=0;
  HuffTree[i].flag=0;
  HuffTree[i].left=-1;
  HuffTree[i].right=-1;
 }
 //構造赫夫曼樹HuffTree的n-1個非葉結點
 for(i=0;i<n-1;i++)
 {m1=m2=MaxV;
  x1=x2=0;
  for(j=0;j<n+i;j++)
  {if(HuffTree[j].weight<m1&&HuffTree[j].flag==0)
    {m2=m1;
     x2=x1;
     m1=HuffTree[j].weight;
     x1=j;
    }
   else if(HuffTree[j].weight<m2&&HuffTree[j].flag==0)
    {m2=HuffTree[j].weight;
     x2=j;
    }
  }
  //將找出的兩棵權值最小的子樹合并為一棵子樹
  HuffTree[x1].parent=n+i;
  HuffTree[x2].parent=n+i;
  HuffTree[x1].flag=1;
  HuffTree[x2].flag=1;
  HuffTree[n+i].weight=HuffTree[x1].weight+HuffTree[x2].weight;
  HuffTree[n+i].left=x1;
  HuffTree[n+i].right=x2;
 }
}
void HuffmanT::HuffCode(int n)
{Code *cd=new Code;
 int child,parent;
 //求n個葉結點的赫夫曼編碼
 for(int i=0;i<n;i++)
 {cd->start=n-1;//不等長編碼的最后一位為n-1
  cd->weight=HuffTree[i].weight;//取得編碼對應權值的字符
  child=i;
  parent=HuffTree[child].parent;
  //由葉結點向上直到根結點
  while(parent!=0)
  {if(HuffTree[parent].left==child)
    cd->bit[cd->start]=0;//左孩子結點編碼0
   else
    cd->bit[cd->start]=1;//右孩子結點編碼1
   cd->start--;
   child=parent;
   parent=HuffTree[child].parent;
  }
  //保存每個葉結點的編碼和不等長編碼的起始位
  for(int j=cd->start+1;j<n;j++)
   huffCode[i].bit[j]=cd->bit[j];
  huffCode[i].start=cd->start;
  huffCode[i].weight=cd->weight;//記住編碼對應權值的字符
 }
}
//赫夫曼編碼問題的測試
void main()
{cout<<"Huffman.cpp運行結果:\n";
 int i,j,n=4;
 int weight[]={1,3,5,7};
 HuffNode *myHuffTree;
 Code *myHuffCode;
 HuffmanT t(myHuffTree,myHuffCode,n);
 if(n>MaxN)
 {cout<<"n越界,修改MaxN!\n";exit(1);}
 t.MakeHufm(weight,n);
 t.HuffCode(n);
 //輸出每個葉結點的赫夫曼編碼
 for(i=0;i<n;i++)
 {cout<<"weight="<<myHuffCode[i].weight<<"  Code=";
  for(j=myHuffCode[i].start+1;j<n;j++)
   cout<<myHuffCode[i].bit[j];
  cout<<endl;
 }
 cin.get();
}