编辑代码

#include <iostream>
#include <queue>
using namespace std;
#define MAXSIZE 8;
typedef struct{
    int weight;
    int parent,lchild,rchild;
}HTNode,*HuffmanTree;
int w[8] = {5,29,7,8,14,23,3,11};
void Select(HuffmanTree HT,int n,int &s1,int &s2){
    HT[0].weight = 9999999;
    s1 = 0;
    s2 = 0;
    for(int i = 1;i<=n;i++){
        if(HT[i].parent==0){
            if(s1==0){
                s1 = i;
                continue;
            }
            if(s2==0){
                s2 = i;
                continue;
            }
            if(HT[s1].weight>HT[i].weight&&HT[s2].weight>HT[i].weight)
                HT[s1].weight>=HT[s2].weight?s1=i:s2=i;
            else if(HT[s1].weight>HT[i].weight)
                s1 = i;
            else if(HT[s2].weight>HT[i].weight)
                s2 = i;
        }
    }
}
void CreateHuffmanTree(HuffmanTree &HT,int n){
    if(n<=1) return ;
    int m = 2*n-1;
    HT = new HTNode[m+1];
    for(int i = 1;i<=m;i++){
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
    }
    for(int i = 1;i<=n;i++){
        HT[i].weight = w[i-1];
    }
    int s1,s2;
    for(int i = n+1;i<=m;i++){
        Select(HT,i-1,s1,s2);
        HT[s1].parent = 1;
        HT[s2].parent = 1;
        HT[i].lchild = s1;
        HT[i].rchild = s2;
        HT[i].weight = HT[s1].weight+HT[s2].weight;
    }
}
void HuffmanTreeTraverse(HuffmanTree HT,int n){
    queue<int>q;
    int e = 1;
    q.push(n);
    while(!q.empty()){
        int i=q.front();
        cout<<" "<<HT[i].weight<<" ";
        if(e==1||e == 3||e==7||e==11)
            cout<<endl;
        e++;
        if(HT[i].lchild != 0)
            q.push(HT[i].lchild);
        if(HT[i].rchild != 0)
            q.push(HT[i].rchild);
        q.pop();
    }

}

int main() {
    HuffmanTree HT;
    CreateHuffmanTree(HT,8);
    HuffmanTreeTraverse(HT,15);
    return 0;
}