建立HUFFMAN树，并进行编码（编码使用无栈非递归方法）

//ps:在进行哈夫曼编码的时候，用了非递归和非栈的情况
//利用了课本上的思想，但是不拘泥于其思想，更容易理解
#include <malloc.h>
#include <stdio.h>

#define SIZE 5

typedef struct
{
int Parent;//双亲的索引
int value;//数据域数值
int left,right;//左右孩子的索引
}* Huffman,Node;

void Select(Huffman &Huff,int start,int end,int &s1,int &s2)
{
//s1<s2<...
int Miner=0x7FFFFFFF;
int Minest=0x7FFFFFFF;
int x_Miner=-1;
int x_Minest=-1;
for(int i=start;i<=end;i++)
{
   if(Huff[i].value<Minest&&0==Huff[i].Parent)
   {
    x_Miner=x_Minest;
    Miner=Minest;
    Minest=Huff[i].value;
    x_Minest=i;
   }
   else
   {
    if(Huff[i].value<Miner&&0==Huff[i].Parent)
    {
     Miner=Huff[i].value;
     x_Miner=i;
    }
   }
}
s1=x_Minest;
s2=x_Miner;
return ;

}

//先将Huffman的数组建好
void HuffmanCoding(int (&HT)[SIZE])
{
int s1(0),s2(0);
int NodeNumber=2*SIZE-1;

Huffman HuffmanArray=(Huffman)malloc(NodeNumber*sizeof(Node));//哈夫曼数组已经编好了

for(int i=0;i<SIZE;i++)
{
   // HuffmanArray[i]={0,HT[i],0,0};//将Huff中的数，复制到HuffmanArray中
   HuffmanArray[i].value=HT[i];
   HuffmanArray[i].Parent=0;
   HuffmanArray[i].left=-1;
   HuffmanArray[i].right=-1;
  
}
for(int i_c=i;i_c<NodeNumber;i_c++)
{
   HuffmanArray[i_c].Parent=0;//把其余节点的Parent都置为0
}
//开始建立节点了
for(;i<NodeNumber;i++)
{
   Select(HuffmanArray,0,i-1,s1,s2);//从0节点到i-1节点找两个最小数，返回
   HuffmanArray[i].value=HuffmanArray[s1].value+HuffmanArray[s2].value;
   HuffmanArray[i].left=s1;
   HuffmanArray[i].right=s2;
   HuffmanArray[s1].Parent=i;
   HuffmanArray[s2].Parent=i;
}
//HuffmanArray[i-1].Parent=0;
//建好节点后，就开始编码了吧

//编码空间最大为：n-1


char * charArray=(char *)malloc((SIZE-1)*sizeof(char));

// Huffman p=(Huffman)malloc(SIZE*sizeof(Node));
int n=0;
Huffman p=&HuffmanArray[n];

for(i=0;i<NodeNumber;i++)
   p[i].value = 0;
p=&p[--i];

int count = 0;
while(count < SIZE)
{
   if(p->value==0)
   {
    p->value=1;//说明遍历过了左边
    if(p->left>=0)
    {
     p=&HuffmanArray[p->left];
     charArray[n++]='0';
    }
    else
    {
     printf("第%d个节点的编码:\n",p-HuffmanArray+1);
     for(int i_i=0;i_i<n;i_i++)
     {
      printf("->%c",charArray[i_i]);
     }
     count++;
     printf("\n");
     n--;
     p=&HuffmanArray[p->Parent];//上溯了
    }
   }
   else if(p->value==1)//说明遍历过了右边
   {
    p->value=2;
    if(p->right>=0)
    {
     p=&HuffmanArray[p->right];
     charArray[n++]='1';
    }//end if 如果p->right=0,那么开始上溯
    else
    {
     //如果p->right==0,那么肯定不是二叉树了，哈哈
    
    
    }
   }
   else if(p->value==2)
   {
   // p->value=0;
    n--;
    p=&HuffmanArray[p->Parent];
  
   
   }

  
}
}

void main()
{
int a[SIZE]={0};
for(int i=0;i<SIZE;i++)
{
   a[i]=i+1;
}
//int * b=a;
HuffmanCoding(a);
}