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->insertAsRoot ( HuffChar ( '^', s1->root()->data.weight + s2->root()->data.weight ) ); 0013 s->attachAsLC ( s->root(), s1 ); s->attachAsRC ( s->root(), s2 ); 0014 forest->insert ( s ); //将合并后的Huffman树插回Huffman森林 0015 } 0016 HuffTree* tree = forest->delMax(); //至此,森林中的最后一棵树 0017 return tree; //即全局Huffman编码树 0018 }