1 #include<iostream>  2 #include<string>  3 using namespace std;  4 #define MAX 20  5   6 /*  7 ** 用二叉树表示的Huffman节点  8 */  9 typedef struct NodeTag { 10     char c;                     // 字母 11     int weight;                 // 频率 12     string code;                // 编码后的字符串 13     struct NodeTag * lchild;    // 左孩子 14     struct NodeTag * rchild;    // 右孩子 15 } Node;  16  17  18 class Container { 19      20     private: 21         Node *nodes[MAX];       // 保存各节点指针的数组 22         int size;               // 节点的个数 23      24     public: 25         Container () { 26             size = 0; 27             for ( int i = 0; i < MAX; i++ ) { 28                 nodes[i] = NULL; 29             } 30         } 31          32         /* 33         ** 采用插入排序的方法，将节点node加入到数组nodes中，按照weight从小到大排列 34         */ 35         void push ( Node *node ) { 36             int weight = node->weight; 37             int i = size-1; 38             while ( i >= 0 && weight > nodes[i]->weight ) { 39                 nodes[i+1] = nodes[i]; 40                 i--; 41             } 42             nodes[i+1] = node; 43             size++; 44         } 45  46         /* 47         ** 返回weight值最小的一个节点 48         */ 49         Node * pop () { 50             Node *node = nodes[size-1];  51             size--; 52             return node; 53         } 54          55         /* 56         ** 返回当前的节点数目 57         */ 58         int getSize() { 59             return size; 60         } 61      62 }; 63  64 /* 65 ** 对所有的叶子节点进行编码，得到各字母的码表 66 ** root：指向根节点的指针；code：本节点的编码 67 */ 68 int huffmanCode( Node *root, const string code ) { 69  70     root->code = code; 71     string temp; 72  73     if( root != NULL ){ 74  75         // 叶子节点，则输出编码方式 76         if( root->rchild == NULL && root->lchild == NULL ) { 77             cout<<root->c<<":"<<root->weight<<" "<<root->code<<endl; 78         } else { 79             temp = code; 80             huffmanCode ( root->lchild, temp.append("0") );   // 会增加上去，不用重新赋值 81             temp = code; 82             huffmanCode ( root->rchild, temp.append("1") ); 83         } 84  85     } 86  87     return 0; 88  89 } 90  91 /* 92 ** Huffman编码的函数 93 ** letter：字母表；weight：各字母的频率；length：字母的总个数 94 */ 95 void haffman ( char letter[], int weight[], int length ) { 96  97     Node *node = NULL; 98     Node *first = NULL; 99     Node *second = NULL;100     Container *obj = NULL;101     102     obj = new Container();103     104     for ( int i = 0; i < length; i++ ) {105         /*106         ** 创建一个新节点node,节点字符为c[i],频率为weight[i],左右孩子都为Null;107         ** 将node按从小到大的顺序加入到容器obj中;108         */109         node = new Node();110         node->c = letter[i];111         node->weight = weight[i];112         node->lchild = NULL;113         node->rchild = NULL;114         obj->push(node);115     }116     117     cout<<"All nodes are pushed into the queue:"<<obj->getSize()<<endl;118     119     /*120     ** 当容器中只有一个元素时，该元素即为指向Huffman编码二叉树的根节点的指针121     */122     while ( obj->getSize() > 1 ) {123         /*124         ** 选出最小的两个元素,创建一个新的父节点,频率为两者之和,将父节点加入到队列中;125         */126         first = obj->pop();127         second = obj->pop();128         node = new Node();129         node->weight = first->weight + second->weight;   // 非根节点的字母不重要，故不用赋值130         node->lchild = first;131         node->rchild = second;132         obj->push(node);133     }134     135     cout<<"After the Haffman code:"<<obj->getSize()<<endl;136     137     /*138     ** 采用中根次序遍历方法对二叉树进行遍历，得到每个叶子节点的编码139     */140     node = obj->pop();141     cout<<node->weight<<endl;142     huffmanCode( node, "");143     144 }145 146 int main () {147     char letter[] = {‘a‘, ‘b‘, ‘c‘, ‘d‘, ‘e‘, ‘f‘, ‘g‘, ‘h‘};148     int weight[] = {1, 1, 2, 3, 5, 8, 13, 21};149     int length = 8;150     haffman( letter, weight, length );151     return 0;152 }