# 2.71

## 练习 2.71 假定我们有一棵n个符号的字母表的Huffman树，其中各符号的相对频度分别是1，2，4，…，$2^{n-1}$。请对n=5和n=10勾勒出有关的树的样子。对于这样的树（对于一般的n），编码出现最频繁的符号用多少个二进制位？最不频繁的符号呢？


(define (make-leaf-set pairs)
(if (null? pairs)
'()
(let ((pair (car pairs)))
(make-leaf-set (cdr pairs))
)
)
)
)

(cond
((null? set) (list x))
((<= (weight x) (weight (car set))) (cons x set))
(else (cons (car set) (adjoin-set x (cdr set))))
)
)

(define (leaf? object) (eq? (car object) 'leaf))

(define (left-branch tree)
(car tree)
)

(define (right-branch tree)
(if (null? (cdr tree))
'()
)
)

(define (encode-symbol-with-code char tree code)
(if (leaf? tree)
(if (eq? (symbol-leaf tree) char)
(list code)
'()
)

(let
(
(left (encode-symbol-with-code char (left-branch tree) '0))
(right (encode-symbol-with-code char (right-branch tree) '1))
)

(let
(
(res (append left right))
)

(if (null? res)
'()
(append (list code) res)
)
)
)
)
)

(define (encode-symbol char tree)
; (encode-symbol-with-code char tree '0)

(if (leaf? tree)
(if (eq? (symbol-leaf tree) char)
(list '0)
'()
)

(let
(
(left-res (encode-symbol-with-code char (left-branch tree) '0))
(right-res (encode-symbol-with-code char (right-branch tree) '1))
)

(append left-res right-res)
)
)
)

(define (decode bits tree)
(define (decode-1 bits current-branch)
(if (null? bits)
'()
(let
(
(next-branch
(choose-branch
(car bits)
current-branch
)
)
)

(if (leaf? next-branch)
(cons
(symbol-leaf next-branch)
(decode-1 (cdr bits) tree)
)
(decode-1 (cdr bits) next-branch)
)
)
)
)

(decode-1 bits tree)
)

(define (choose-branch bit branch)
(cond
((= bit 0) (left-branch branch))
((= bit 1) (right-branch branch))
(else
(error "bad bit -- CHOOSE-BRANCH" bit)
)
)
)

(define (make-leaf symbol weight)
(list 'leaf symbol weight)
)

(define (leaf? object)
(eq? (car object) 'leaf)
)

(define (make-code-tree left right)
(list
left
right
(append (symbols left) (symbols right))
(+ (weight left) (weight right))
)
)

(define (symbols tree)
(if (leaf? tree)
(list (symbol-leaf tree))
)

(define (weight tree)
(if
(leaf? tree)
(weight-leaf tree)
)
)

(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-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 (successive-merge sorted-leaf-set)
(if (<= (length sorted-leaf-set) 1)
sorted-leaf-set
(let
(
(left (car sorted-leaf-set))
)

(let
(
(new-leaf (make-code-tree left right))
(rest (cddr sorted-leaf-set))
)

(if (null? rest)
new-leaf
(successive-merge
)
)
)
)
)
)

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

(define (encode message tree)
(if (null? message)
'()
(append
(encode-symbol (car message) tree)
(encode (cdr message) tree)
)
)
)


(define n5 (list
(list 'A 1)
(list 'B 2)
(list 'C 4)
(list 'D 8)
(list 'E 16)
)
)

(define huffman5 (generate-huffman-tree n5))

huffman5


(define n10 (list
(list 'A 1)
(list 'B 2)
(list 'C 4)
(list 'D 8)
(list 'E 16)
(list 'F 32)
(list 'G 64)
(list 'H 128)
(list 'I 256)
(list 'J 512)
)
)

(define huffman10 (generate-huffman-tree n10))

huffman10