0001 // forest基于优先级队列实现，此算法适用于符合PQ接口的任何实现方式
0002 // 为Huffman_PQ_List、Huffman_PQ_ComplHeap和Huffman_PQ_LeftHeap共用
0003 // 编译前对应工程只需设置相应的标志：DSA_PQ_List、DSA_PQ_ComplHeap或DSA_PQ_LeftHeap
0004 HuffTree generateTree( HuffForest* forest ) { //由Huffman森林，构造出Huffman编码树
0005    while ( 1 < forest->size() ) { //每迭代一步，森林中都会减少一棵树
0006       HuffTree T1 = forest->delMax(), T2 = forest->delMax(); //取出权重最小的两棵树
0007       HuffTree S; //将其合并成一棵新树
0008       S.insert( HuffChar ( '^', T1.root()->data.weight + T2.root()->data.weight ) );
0009       S.attach( T2, S.root() ); S.attach( S.root(), T1 ); //T2权重不小于T1
0010       forest->insert( S ); //再插回至森林
0011    } //森林中最终唯一所剩的那棵树，即Huffman编码树（且其层次遍历序列必然单调非增）
0012    return forest->delMax(); //故返回之
0013 }