0001 /******************************************************************************************
0002  * Huffman树构造算法：对传入的Huffman森林forest逐步合并，直到成为一棵树
0003  ******************************************************************************************
0004  * forest基于优先级队列实现，此算法适用于符合PQ接口的任何实现方式
0005  * 为Huffman_PQ_List、Huffman_PQ_ComplHeap和Huffman_PQ_LeftHeap共用
0006  * 编译前对应工程只需设置相应标志：DSA_PQ_List、DSA_PQ_ComplHeap或DSA_PQ_LeftHeap
0007  ******************************************************************************************/
0008 HuffTree* generateTree ( HuffForest* forest ) {
0009    while ( 1 < forest->size() ) {
0010       HuffTree* s1 = forest->delMax(); HuffTree* s2 = forest->delMax();
0011       HuffTree* s = new HuffTree();
0012       s->insert ( HuffChar ( '^', s1->root()->data.weight + s2->root()->data.weight ) );
0013       s->attach ( s1, s->root() ); s->attach ( s->root(), s2 );
0014       forest->insert ( s ); //将合并后的Huffman树插回Huffman森林
0015    }
0016    HuffTree* tree = forest->delMax(); //至此，森林中的最后一棵树
0017    return tree; //即全局Huffman编码树
0018 }