哈夫曼树

//哈夫曼树的简单解释：就是带权最短路径查找树。
//https://blog.csdn.net/shuangde800/article/details/7341289

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#include <iostream>
using namespace std;
/**
*                   Huffman类 
*/ 

class HuffmanTreeNode{
    public:
    int weight;//权重
    int parent,lchild,rchild; 
};       

typedef HuffmanTreeNode *   HuffmanTree;            //声明一个HuffmanTreeNode类型的HuffmanTree 

HuffmanTree HuffmanCoding(char** &HC,int w[],char a[],int n);       //Huffman编码
void Select(HuffmanTree HT,int n,int&s1,int&s2); 
void PrintHffmanCode(char** &HC,int w[],char code[],int codeLen,int a[],int aLen );

//选出两个权值最小的节点 
void Select(HuffmanTree HT,int n,int&s1,int&s2){
    int i=1,j;
    while(HT[i].parent!=0)
        i++;
    j=i+1;
    while(HT[j].parent!=0)
        j++;
    if(HT[i].weight>HT[j].weight){
        s1=j;               //s1为权重小的
        s2=i;
    }else{
        s1=i;
        s2=j;
    }
    i=j+1;
    while(i<=n){
        if(HT[i].parent!=0)
            i++;
        else if(HT[i].weight<HT[s1].weight){
            s2=s1;
            s1=i;
        }else if(HT[i].weight<HT[s2].weight)
            s2=i;
        i++;
    }

}
//Huffman编码 
HuffmanTree HuffmanCoding(char **& HC,int w[],char a[],int n){
    int i,start,c,f;
    HuffmanTreeNode *p;
    char *cd;
    if(n<1)return NULL;

    int m=2*n-1;
    //定义一个有m+1个节点的霍夫曼树
    HuffmanTree HT=new HuffmanTreeNode[m+1]; 
    //初始化
    for(p=HT+1,i=1;i<=n;i++,p++){
        p->weight=w[i-1];
        p->lchild=0;
        p->rchild=0;
        p->parent=0;
    } 
    int s1,s2;
    for(;i<=m;++i){
        Select(HT,i-1,s1,s2);       
        HT[s1].parent=i;
        HT[s2].parent=i;
        HT[i].parent=0;
        HT[i].lchild=s1;
        HT[i].rchild=s2;
        HT[i].weight=HT[s1].weight+HT[s2].weight;       //父节点weight值为左右孩子的权值之和 
    }

    HC=new char* [n];
    cd=new char[n];            
    cd[n-1]='\0';                                
    for(i=1;i<=n;++i){
        start=n-1;                               
        for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){
            if(HT[f].lchild==c)
                cd[--start]='0';
            else
                cd[--start]='1';
        }
        HC[i-1]=new char[n-start];
        strcpy(HC[i-1],&cd[start]);                   
    }
    return HT;
}
 
void PrintHffmanCode(char** &HC,int w[],char code[],int codeLen,int aLen ) { 
    HuffmanTree HT=HuffmanCoding(HC,w,code,codeLen);
    for(int r=0;r<codeLen;r++){
       cout<<code[r]<<"的字符的赫夫曼编码为:"<<HC[r]<<endl;
    }
}
void main(){
    int len;
    char *A;
    int *w;
    char **codeA;
    int n;
    cout<<"输入元素个数：";
            cin>>len;
            A=new char[len];
            w=new int[len];
            for(n=0;n<len;n++){
                cout<<"输入第"<<n+1<<"个元素：";
                cin>>A[n];
                cout<<"输入对应权值：";
                cin>>w[n];
            }
            HuffmanCoding(codeA,w,A,len);
            PrintHffmanCode(codeA,w,A,len,len);
    system("pause");
}