在书本 111 到 112 页的『生成 Huffman 树』小节,已经很详细地说明了 Huffman 树的生成过程了, generate-huffman-tree
就是这一过程的程序化表示:
;;; 69-generate-huffman-tree.scm
(load "p113-adjoin-set.scm")
(load "p114-make-leaf-set.scm")
(define (generate-huffman-tree pairs)
(successive-merge (make-leaf-set pairs)))
(define (successive-merge ordered-set)
(cond ((= 0 (length ordered-set))
'())
((= 1 (length ordered-set))
(car ordered-set))
(else
(let ((new-sub-tree (make-code-tree (car ordered-set)
(cadr ordered-set)))
(remained-ordered-set (cddr ordered-set)))
(successive-merge (adjoin-set new-sub-tree remained-ordered-set))))))
因为 successive-merge
接受的是有序集合(按权重值从低到高排列,用一个列表表示),所以我们可以这样来生成 Huffman 树:
0
,那么返回空表 '()
1
,那么返回列表的 car
部分,也即是,取出列表中(已经生成完毕)的 Huffman 树1
,也即是说,集合中至少有两个元素,那么根据集合已排序的原则,列表最前面的两个元素肯定是集合所有元素中权重最少的两个,因此,调用 make-code-tree
组合起这两个元素,得出新子树,并从表示集合的列表中删除这两个元素,得出新集合,然后使用函数 adjoin-tree
,将新子树有序地加入到新集合中去以上步骤最重要的就是使用 adjoin-tree
保持新列表也是有序的,所以组合树的操作可以继续有序地进行。
另外要指出的一点是,当 successive-merge
第一次被调用时,它接受的列表中的所有元素都是树叶,但是之后这个列表里就既有树叶,也有树了,因为我们使用通用的 weight
提取它们的权重,所以不会遇到列表中有两类元素需要处理的麻烦,这也体现了通用操作的威力。
测试:
1 ]=> (load "69-generate-huffman-tree.scm")
;Loading "69-generate-huffman-tree.scm"...
; Loading "p113-adjoin-set.scm"...
; Loading "p112-huffman.scm"... done
; ... done
; Loading "p114-make-leaf-set.scm"...
; Loading "p113-adjoin-set.scm"...
; Loading "p112-huffman.scm"... done
; ... done
; ... done
;... done
;Value: successive-merge
1 ]=> (generate-huffman-tree '((A 4) (B 2) (C 1) (D 1)))
;Value 13: ((leaf a 4) ((leaf b 2) ((leaf d 1) (leaf c 1) (d c) 2) (b d c) 4) (a b d c) 8)