Exercise 2.67. Define an encoding tree and a sample message:
(define sample-tree
(make-code-tree (make-leaf 'A 4)
(make-code-tree
(make-leaf 'B 2)
(make-code-tree (make-leaf 'D 1)
(make-leaf 'C 1)))))
(define sample-message '(0 1 1 0 0 1 0 1 0 1 1 1 0))
Use the decode procedure to decode the message, and give the result.
直接使用 decode 即可得到结果：
(load "huffman-tree.scm")
(define sample-tree
(make-code-tree (make-leaf 'A 4)
(make-code-tree
(make-leaf 'B 2)
(make-code-tree (make-leaf 'D 1)
(make-leaf 'C 1)))))
(define sample-message '(0 1 1 0 0 1 0 1 0 1 1 1 0))
;(decode sample-message sample-tree)
; (a d a b b c a)再简单画图更直观地看看
huffman tree
({a b c d}, 8)
/ \
/ \
/ \
(a, 4) ({b c d}, 4)
/ \
/ \
/ \
(b, 2) ({c d}, 2)
/ \
/ \
/ \
(d, 1) (c, 1)
0 向左边子树移动，1 向右边子树移动。对于 (0 1 1 0 0 1 0 1 0 1 1 1 0) 就可以得到 (a d a b b c a)。