树和二叉树_4

一、最优变长编码：哈夫曼树

获得最优变长编码，使用哈夫曼树。
背景：需要对不同的字符进行编码，需要让编码尽可能短，且不能有重复前部，不然无法识别。
哈夫曼树构造方法：选取出现概率值最低的两个节点构成二叉树，合成一个概率为二者之和的节点加入节点队列中，不断重复此过程即可。

二、代码实现

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>

typedef struct Node{
    char ch;
    int freq;
    struct Node *lchild,*rchild;
} Node;
Node *getNewNode(char ch,int freq){
    Node *p=(Node *)malloc(sizeof(Node));
    p->ch=ch;
    p->freq=freq;
    p->lchild=p->rchild=NULL;
    return p;
}
void clear(Node *root){
    if(root==NULL) return ;
    clear(root->lchild);
    clear(root->rchild);
    free(root);
    return ;
}
void swap_node(Node **node_arr,int i,int j){
    Node *temp=node_arr[i];
    node_arr[i]=node_arr[j];
    node_arr[j]=temp;
    return ;
}
int find_min_node(Node **node_arr,int n){
    int index=0;
    for(int j=1;j<=n;j++){
        if(node_arr[index]->freq>node_arr[j]->freq) index=j;
    }
    return index;
}
Node *buildHaffmanTree(Node **node_arr,int n){
    for(int i=1;i<n;i++){
        //找到最小的两个节点 
        int index1=find_min_node(node_arr,n-i);
        swap_node(node_arr,index1,n-i);
        int index2=find_min_node(node_arr,n-i-1);
        swap_node(node_arr,index2,n-i-1);
        //合并这两个节点 ，把新节点放到n-i-1位置 
        int freq=node_arr[n-i]->freq+node_arr[n-i-1]->freq;
        Node *node=getNewNode(freq,0);
        node->lchild=node_arr[n-i-1];
        node->rchild=node_arr[n-i];
        node_arr[n-i-1]=node;
    }
    return node_arr[0];
}
void extraHaffman(Node *root,char buff[],int k){
    buff[k]=0;//字符串末尾0截断，如果为叶子节点输出 
    if(root->lchild==NULL&&root->rchild==NULL){
        printf("%c : %s\n",root->ch,buff);
        return ;
    }
    buff[k]='0';
    extraHaffman(root->lchild,buff,k+1);
    buff[k]='1';
    extraHaffman(root->rchild,buff,k+1);
    return ;
}

int main(){
    int n,freq;
    char s[10];
    scanf("%d",&n);
    Node **node_arr=(Node **)malloc(sizeof(Node *)*n);
    for(int i=0;i<n;i++){
        scanf("%s%d",s,&freq);
        node_arr[i]=getNewNode(s[0],freq);
    }
    Node *root=buildHaffmanTree(node_arr,n);
    char buff[1000];
    extraHaffman(root,buff,0);//路径前缀长度 
    clear(root);
    return 0;
}