Exercise 2.69 · 习题

Exercise 2.69: The following procedure takes as
its argument a list of symbol-frequency pairs (where no symbol appears in more
than one pair) and generates a Huffman encoding tree according to the Huffman
algorithm.

(define (generate-huffman-tree pairs)
(successive-merge
(make-leaf-set pairs)))

Make-leaf-set is the procedure given above that transforms the list of

pairs into an ordered set of leaves. Successive-merge is the procedure

you must write, using make-code-tree to successively merge the

smallest-weight elements of the set until there is only one element left, which

is the desired Huffman tree. (This procedure is slightly tricky, but not

really complicated. If you find yourself designing a complex procedure, then

you are almost certainly doing something wrong. You can take significant

advantage of the fact that we are using an ordered set representation.)

练习 2.69：以下过程以符号-频率序对的表（其中每个符号出现在至多一个序对中）为参数，按照哈夫曼算法生成哈夫曼编码树。

(define (generate-huffman-tree pairs)
(successive-merge
(make-leaf-set pairs)))

make-leaf-set 是前面给出的过程，它将序对表转换为有序的叶节点集合。successive-merge 是你必须编写的过程，利用 make-code-tree 依次合并集合中权重最小的元素，直到集合中只剩一个元素，该元素即为所求的哈夫曼树。（这个过程略有技巧性，但并不真正复杂。若你发现自己在设计一个复杂的过程，几乎可以肯定你的做法有误。可以充分利用我们使用有序集合表示这一事实。）