#include
using namespace std;
typedef struct
{
int Weight;
bool paixflag;
bool flag;
int par;
int lch;
int rch;
}HuffNode,*pHuffNode;
typedef struct
{
int n;
int root;
HuffNode *Huf;
}HuffTree,*pHuffTree;
HuffTree * InitHuffman(int w[],int n){
if(n
HuffTree *Tree = new HuffTree(); Tree->n = n;
Tree->Huf = new HuffNode[2*n-1];
for(int i=0;i
Tree->Huf[i].flag = 0;
Tree->Huf[i].lch = -1;
Tree->Huf[i].rch = -1;
Tree->Huf[i].par = -1;
Tree->Huf[i].Weight = (i<n)?w[i]:999999;
}
return Tree;
}
void GetSmallTwo(HuffNode *Num,int n,int &m1,int &m2){//每次取得新数组的两个flag为0的最小值
for(int i=0;i<2*n-1;i++){
for(int j=i+1;j<2*n-1;j++){
if(Num[i].Weight>Num[j].Weight){
int temp = Num[i].Weight;
Num[i].Weight = Num[j].Weight;
Num[j].Weight = temp;
}
}
}
for(int i=0;i<2*n-1;i++){
if(Num[i].flag==0){
m1 = Num[i].Weight;
m2 = Num[i+1].Weight;
break;
}
}
}
HuffTree* CreateHuffman(int w[],int n){
HuffTree *HTree = InitHuffman(w,n);
int i = 0,j = 0,m1 = 0,m2 = 0,x1,x2;
for(i=0;i
GetSmallTwo(HTree->Huf,n,m1,m2);
x1 = 0;x2 = 0;
for(j=0;j<n+i;j++){
if(!HTree->Huf[j].flag){
if(HTree->Huf[j].Weight==m1){
x1 = j;
cout<<endl<<"x1-->"<<x1<<endl;
}else if(HTree->Huf[j].Weight==m2){
x2 = j;
cout<<endl<<"x2-->"<<x2<<endl;
}
}
}
HTree->Huf[x1].par = n+i;
HTree->Huf[x2].par = n+i;
HTree->Huf[x2].flag = 1;
HTree->Huf[x1].flag = 1;
HTree->Huf[n+i].Weight = HTree->Huf[x1].Weight+HTree->Huf[x2].Weight;
HTree->Huf[n+i].lch = x1;
HTree->Huf[n+i].rch = x2;
}
return HTree;
}
int main(){
int num[7] = {3,1,7,5};
HuffTree Tree = /*InitHuffman(num,10);///CreateHuffman(num,4);
cout<<"[K]"<<"Weight "<<"LRCHIL "<<"RRCHIL "<<"PARENT "<<"flag "<<endl;
for(int i=0;i<7;i++){
cout<<"["<<i<<"] "<<Tree->Huf[i].Weight<<" "<<Tree->Huf[i].lch<<" "<<Tree->Huf[i].rch<<" "<<Tree->Huf[i].par<<" "<<Tree->Huf[i].flag<<endl;
}
/*for(int i=0;i<10;i++){
cout<<cout<<"HTree->Huf["<<i<<"].Weight-->"<<Tree->Huf[i].Weight<<endl;
cout<<i<<"--->flag"<<Tree->Huf[i].flag<<endl;
cout<<i<<"--->son"<<Tree->Huf[i].lch<<endl;
}
int m1,m2;
GetSmallTwo(Tree->Huf,10,m1,m2);
cout<<m1<<" "<<m2<<endl;
GetSmallTwo(Tree->Huf,10,m1,m2);
cout<<m1<<" "<<m2<<endl;
GetSmallTwo(Tree->Huf,10,m1,m2);
cout<<m1<<" "<<m2<<endl;
GetSmallTwo(Tree->Huf,10,m1,m2);
cout<<m1<<" "<<m2<<endl;
GetSmallTwo(Tree->Huf,10,m1,m2);
cout<<m1<<" "<<m2<<endl;
for(int i=0;i<10;i++){
cout<<cout<<"HTree->Huf["<<i<<"].Weight-->"<<Tree->Huf[i].Weight<<endl;
cout<<i<<"--->flag"<<Tree->Huf[i].flag<<endl;
cout<<i<<"--->son"<<Tree->Huf[i].lch<<endl;
}*/
system("pause");
return 0;
}