数据结构——Huffman-Tree

  1 #include<iostream>
  2 #include<stdlib.h>
  3 using namespace std;
  4 
  5 //- - - 定义哈夫曼树的结点结构体 - - -
  6 typedef struct
  7 {
  8     int weight;     //权值
  9     int parent;     //父结点
 10     int lchild;
 11     int rchild;
 12 }HTNode;
 13 
 14 HTNode HfNode[1000];    //结构体数组,随便开个范围吧╮(╯▽╰)╭
 15 
 16 //- - - 定义哈夫曼编码结构体 - - -
 17 typedef struct
 18 {
 19     int code[1000];   //存储编码
 20     int start;        //编码下标
 21 }HufCode;
 22 
 23 HufCode HfCode[1000];
 24 
 25 //- - - 构造哈夫曼树 - - -
 26 void CreateHuffmanTree(HTNode HfNode[1000],int n)
 27 {
 28     int i,j;
 29     int min1,min2;  //表示两个最小的权值
 30     int x1,x2;    //表示两个最小权值结点对应的下标序号
 31 
 32     //n个叶子的哈夫曼树共有2n-1个结点
 33     //初始化结点信息
 34     for(i=0;i<2*n-1;i++)
 35     {
 36         HfNode[i].weight=0;
 37         HfNode[i].parent=0;
 38         HfNode[i].lchild=0;
 39         HfNode[i].rchild=0;
 40     }
 41     //输入n个叶子结点的权值
 42     cout<<"请输入各叶子的权值:"<<endl;
 43     for(i=0;i<n;i++)
 44     {
 45         cin>>HfNode[i].weight;
 46     }
 47     cout<<"哈夫曼树结点从下(叶子)往上(跟)从左往右结点信息依次是:"<<endl;
 48     //开始构造
 49     for(i=0;i<n-1;i++)
 50     {
 51         //初始化
 52         min1=min2=666666; //因为min1,min2代表两个最小的权值，所以初始化设为一个很大的数
 53         x1=x2=-666666;
 54 
 55         for(j=0;j<i+n;j++)
 56         {
 57             if(HfNode[j].weight<min1&&HfNode[j].parent==0)
 58             {
 59                 //通过这样来实现信息的迭代更新
 60                 min2=min1;
 61                 min1=HfNode[j].weight;
 62                 x2=x1;
 63                 x1=j;
 64             }
 65             else if(HfNode[j].weight<min2&&HfNode[j].parent==0)
 66             {
 67                 min2=HfNode[j].weight;
 68                 x2=j;
 69             }
 70         }
 71         //更新信息
 72         HfNode[x1].parent=n+i;
 73         HfNode[x2].parent=n+i;
 74         //新结点信息
 75         HfNode[n+i].weight=min1+min2;
 76         HfNode[n+i].lchild=x1;
 77         HfNode[n+i].rchild=x2;
 78         cout<<HfNode[x1].weight<<" "<<HfNode[x2].weight<<endl;
 79     }
 80 }
 81 //- - - 哈夫曼编码 - - -
 82 void CreateHuffmanCode(HufCode HfCode[1000],int n)
 83 {
 84     HufCode cd;      //定义一个临时变量来存放信息
 85     int i,j;
 86     for(i=0;i<n;i++)
 87     {
 88         cd.start=n-1;
 89         int xb=i;    //下标
 90         int p=HfNode[xb].parent;     //记录父结点信息
 91         while(p!=0)
 92         {
 93             //左儿子0，右儿子1
 94             if(HfNode[p].lchild==xb)
 95                 cd.code[cd.start]=0;
 96             else
 97                 cd.code[cd.start]=1;
 98             cd.start--; //编码下表向前移动一位
 99             xb=p;        //迭代更替
100             p=HfNode[xb].parent;
101         }
102         for(j=cd.start+1;j<n;j++)
103         {
104             HfCode[i].code[j]=cd.code[j];
105         }
106         HfCode[i].start=cd.start;
107     }
108 }
109 
110 int main()
111 {
112     int n;
113     cout<<"请输入叶子数n:"<<endl;
114     cin>>n;
115     CreateHuffmanTree(HfNode,n);
116     CreateHuffmanCode(HfCode,n);
117     for(int i=0;i<n;i++)
118     {
119         cout<<HfNode[i].weight<<"对应的哈夫曼编码是: ";
120         for(int j=HfCode[i].start+1;j<n;j++)
121         {
122             cout<<HfCode[i].code[j];
123         }
124         cout<<"
";
125     }
126     return 0;
127 }