哈夫曼树

#include<bits/stdc++.h>

using namespace std;

const int N=1000;

typedef struct HNode{
    char ch;
    int weight;
    HNode *lchild,*rchild;
}*HTree;

HTree CreateHuffmanTree(int arr1[],char arr2[],int n){
    HTree forest[N];
    HTree root=NULL;
    for(int i=0;i<n;i++){
        HTree temp;
        temp=(HTree)malloc(sizeof(HNode));
        temp->ch=arr2[i];
        temp->weight=arr1[i];
        temp->lchild=NULL;
        temp->rchild=NULL;
        forest[i]=temp;
    }

    for(int i=1;i<n;i++){
        int minn=-1;
        int secminn;
        for(int j=0;j<n;j++){
            if(forest[j]!=NULL&&minn==-1){
                minn=j;
                continue;
            }
            if(forest[j]!=NULL){
                secminn=j;
                break;
            }
        }

        for(int j = secminn;j<n;j++){
            if(forest[j]!=NULL){
                if(forest[j]->weight<forest[minn]->weight){
                    secminn=minn;
                    minn=j;
                }else{
                    if(forest[j]->weight<forest[secminn]->weight){
                        secminn=j;
                    }
                }
            }

        }
        root=(HTree)malloc(sizeof(HNode));
        root->weight=forest[minn]->weight+forest[secminn]->weight;
        root->lchild=forest[minn];
        root->rchild=forest[secminn];

        forest[minn]=root;
        forest[secminn]=NULL;
    }
    return root;
}

void HuffmanCode(HTree root,int len,int arr[]){
    if(root!=NULL){
        if(root->lchild==NULL&&root->rchild==NULL){
            cout<<"字符"<<root->ch<<"的编码为";
            for(int i=0;i<len;i++){
                cout<<arr[i];
            }
            cout<<endl;
        }
        else{
            arr[len]=0;
            HuffmanCode(root->lchild,len+1,arr);
            arr[len]=1;
            HuffmanCode(root->rchild,len+1,arr);
        }
    }
}
int main(){
    int x;
    cout<<"数据的个数是：";
    cin>>x;
    int num[x];
    char letter[x];
    cout<<"请输入字符和它的权重"<<endl;
    for(int i=0;i<x;i++){
        cin>>letter[i]>>num[i];
    }
    CreateHuffmanTree(num,letter,x);
    HuffmanCode(CreateHuffmanTree(num,letter,x),0,num);

    return 0;
}