构造哈夫曼树

//构造哈夫曼树
#include<iostream>
using namespace std;

typedef struct{
    int weight;
    int parent,lchild,rchild;
}HTNode,*HuffmanTree;

//选出最小的两个
void Select(HuffmanTree HT.int len,int &s1,int &s2){
    int i,min1=0x3f3f3f3f,min2=0x3f3f3f3f;
    for(i=1;i<=len;i++){
        if(HT[i].weight<min1&&HT[i].parent==0){
         min1=HT[i].weight;
         s1=i;   
        }
    }
    int temp=HT[s1].weight;
    HT[s1].weight=0x3f3f3f3f;
    for(i=1;i<=len;i++){
        if(HT[i].weight<min2&&HT[i].parent==0){
            min2=HT[i].weight;
            s2=i;
        }
    }
    HT[s1].weight=temp;
}

void CreateHuffmanTree(HuffmanTree &HT,int n){
    im,s1,s2,i;
    if(n<=1) return;
    m=2*n-1;
    HT=new HTNode[m+1];
    for(i=1;i<m;i++){
        HT[i].parent=0;
        HT[i].lchild=0;
        HT[i].rchild=0;
    } 
    cout<<"please input the weight of leaf child:\n";
    for(i=1;i<n;i++)
        cin>>HT[i]weight;
    for(i=n+1;i<=m;i++){
        Select(HT,i-1;s1,s2);
        HT[s1].parent=i;
        HT[s2].rchild=i;
        HT[i].lchild=s1;
        HT[i].rchild=s2;
        HT[i].weight=HT[s1].weight+HT[s2].weight;
    }
}

void main(){
    HuffmanTree HT;
    int n;
    cout<<"please input the num of leaf child:\n";
    cin>>n;
    CreateHuffmanTree(HT,n);
    cout<<"finish!\n";
}

构造哈夫曼树

原文：https://www.cnblogs.com/ygjzs/p/11874615.html