C语言实现哈夫曼树的方法

#include<stdio.h>
#define MAX_SIZE 1000
typedef struct node Node;
struct NODE{
   int weight;//节点的权值
   int parent,lchild,rchild;
};

void initNode(Node &node,int weight,int parent,int lchild,int rchild){
    node.weight = weight;
    node.lchild = lchild;
    node.rchild = rchild;
    node.parent = parent;
}

void createHuffmanTree(Node *node,int *arr,int n){
    //n表示有n个叶子节点，arr数组存放的是所有叶子节点的值
   int i,j,min1,min2,x1,x2,total;//min1:第一个最小值，min2:第二个最小值,x1:第一个最小值的下标，x2:第二个最小值的下标
   for(i = 0; i < n; i++){
       initNode(node[i],arr[i],-1,-1,-1);//调用initNode方法，从而将节点进行初始化
   }
   total = n * 2 - 1;//total表示的是哈夫曼所有节点的个数
   for(i = n; i < total; i++){
        //i之所以从n开始，是因为第一个父节点这个下标（前n个节点是叶子节点）
        min1 = 65432;//定义两个最小值
        min2 = min1;
        x1 = x2 = 0;//假设两个最小值的下标都是0
        for(j = 0; j < i; j++){
            //判断当前下标的节点是否为叶子节点
           if(node[j].parent == -1){
          //如果当前节点的parent等于-1，表示这个节点是一个叶子节点，那么我们需要判断他是否一个最小节点
                if(node[j].weight < min1){
         //如果当前这个节点的值比min1小，那么我们需要更新min2，min1，同时需要更新两者对应的下标
                    min2 = min1;
                    x2 = x1;
                    min1 = node[j].weight;
                    x1 = j;
                }else if(node[j].weight < min2){
                 
                   min2 = node[j].weight;
                   x2 = j;
                }
           }
        }
        
        node[x1].parent = i;
        node[x2].parent = i;
        initNode(node[i],min1 + min2,-1,x1,x2);//初始化合并之后的新节点
   }
}
void huffmanCode(Node *node,int child,int *str){
    //str表示的是这个叶子节点的哈夫曼编码
    int i,parent,j = 0,e;
    parent = node[child].parent;//获取当前这个叶子节点的父节点
    while(parent != -1){
        if(node[parent].lchild == child){
            //如果当前这个节点是父节点的左子节点，那么就将0压入到数组中,否则将1压入数组中
            str[j++] = 0;
        }else{
            str[j++] = 1;
        }
        child = parent;
        parent = node[child].parent;
    }
    e = j;//当退出循环的时候，j表示的是这个数的哈夫曼编码的长度，所以需要从下标为j - 1开始逆序输出，才是这个数的哈夫曼编码
    for(j = e - 1; j>= 0; j--)
        printf("%d",str[j]);
    printf("\n");
}
int main(){
  Node node[MAX_SIZE];
  int arr[MAX_SIZE];//定义一个整形数组，用于存放所有叶子节点的权值
  int arr2[MAX_SIZE];//arr2用于存放一个数字的哈夫曼编码
  int n,i,j,e;
  printf("请输入叶子节点的个数:");
  scanf("%d",&n);
  for(i = 0; i < n; i++)
    scanf("%d",&arr[i]);
  createHuffmanTree(node,arr,n);//构建哈夫曼树
  
  for(i = 0; i < n; i++){
    huffmanCode(node,i,arr2);//调用这个方法，将当前下标对应的数字的哈夫曼编码输出
  }
  return 0;
}