#ifndef HUFFMAN_H_INCLUDED

 #define HUFFMAN_H_INCLUDED

 #include <iostream>

 #include <stdlib.h>

 #include <string>

 #define leafNumber 20

 #define totalNumber 39

 #define maxValue 100

 using namespace std;

 //权值类型, 这里定义为int

 typedef int WType;

 //树的结点类型, 这里定义为char, 表示字符

 typedef char TElemType;

 //Huffman树结点信息定义

 typedef struct HuffmanNode{

     TElemType data;

     WType weight;

     int left_child;

     int right_child;

     int parent;

     string code;    //每个结点的编码, 定义为 string 类

 };

 //Huffman树结构定义

 typedef struct HuffmanTree{

     HuffmanNode elem[totalNumber];

     int currentNumber;

 };

 /*

 *构建Huffman树

 */

 void createHuffmanTree( HuffmanTree &HT, WType w[], int n ) {

     int i, j, p1, p2, min1, min2;

     for( i = ; i < n; i++ ) HT.elem[i].weight = w[i];

     for( i = ; i <  * n - ; i++ )

         HT.elem[i].parent = HT.elem[i].left_child = HT.elem[i].right_child = -;

     for( i = n; i <  * n - ; i++ ) {

         min1 = min2 = maxValue;

         for( j = ; j < i; j++ ) {

             if( HT.elem[j].parent == - )

                 if( HT.elem[j].weight < min1 ) {

                     p2 = p1;

                     min2 = min1;

                     p1 = j;

                     min1 = HT.elem[j].weight;

                 }

                 else if( HT.elem[j].weight < min2 ) {

                     p2 = j;

                     min2 = HT.elem[j].weight;

                 }

         }

         HT.elem[i].left_child = p1;

         HT.elem[i].right_child = p2;

         HT.elem[i].weight = HT.elem[p1].weight + HT.elem[p2].weight;

         HT.elem[p1].parent = HT.elem[p2].parent = i;

     }

     HT.currentNumber =  * n - ;

 }

 /*

 *对Huffman树每个结点进行编码

 */

 void Coding( HuffmanTree &HT, int n ) {

     //当前节点下标

             int current = ;

             //父节点下标

             int parent = ;

     for( int i =  * n -  ; i >= ; i-- ) {

         current = i;

         parent = HT.elem[current].parent;

         /*

         if( parent == -1 ) HT.elem[current].code[0] = '0';

         else {

             if( HT.elem[parent].left_child == current ) {

                 strcat( HT.elem[current].code, HT.elem[parent].code );

                 strcat( HT.elem[current].code, "0" );

             }

             if( HT.elem[parent].right_child == current ) {

                 strcat( HT.elem[current].code, HT.elem[parent].code );

                 strcat( HT.elem[current].code, "1" );

             }

         }

         */

         while (parent != -)

                 {

                     if (HT.elem[parent].left_child == current) HT.elem[i].code += "";

                     else HT.elem[i].code += "";

                     current = parent;

                     parent = HT.elem[current].parent;

                 }

         //HT.elem[current].code += "0";

         reverse( HT.elem[i].code.begin(), HT.elem[i].code.end() );

     }

 }

 /*

 *译码

 */

 void decode( HuffmanTree &HT, int n ) {

     cout << "输入电文: ";

     char ch[];

     gets( ch );

     int i = ;

     int parent;

     int root =  * n - ;

     int index = root;

     int count = ;

     int len = strlen( ch );

     while( ch[i] != '#' ) {

         if( ch[i] == '' ) {

             index = HT.elem[index].left_child;

             //cout << "经过0" << endl;

             //cout << index << endl;

             //count++;

         }

         else if( ch[i] == '' ) {

             index = HT.elem[index].right_child;

             //cout << "经过1" << endl;

             //cout << index << endl;

             //count++;

         }

         if( HT.elem[index].left_child == - && HT.elem[index].right_child == - ) {

             cout << HT.elem[index].data;

             index = root;

             //i += count;

             //count = 0;

             //cout << index << endl;

         }

         i++;

     }

 }

 /*

 *遍历

 */

 void PreOrder( HuffmanTree &HT, int n ) {

     for( int i = ; i < n; i++ ) {

         cout << "字符: " << HT.elem[i].data << ", " << "权值: " << HT.elem[i].weight << "  Huffman编码: " << HT.elem[i].code << endl;

     }

 };

 #endif // HUFFMAN_H_INCLUDED

#include "Huffman.h"

int main() {

    HuffmanTree HT;

    HT.elem[].data = 'A';

    HT.elem[].data = 'B';

    HT.elem[].data = 'C';

    HT.elem[].data = 'D';

    HT.elem[].data = 'E';

    WType weight[] = { , , , ,  };

    //WType weight[] = { 5,7,2,13 };

    createHuffmanTree( HT, weight,  );

    Coding( HT,  );

    PreOrder( HT,  );

    cout << endl << endl;

    for( int i = ; i < ; i++ )

        cout << "Node " << i << " Code: " << HT.elem[i].code << endl;

    cout << endl << endl;

    for( int i = ; i < ; i++ ) {

        cout << "Node " << i << ": " << "weight = " << HT.elem[i].weight << ", parent = " << HT.elem[i].parent << ", left_child = " << HT.elem[i].left_child

                << ", right_child = " << HT.elem[i].right_child << endl;

    }

    decode( HT,  );

    return ;

}