# 2.68

## 练习 2.68 过程encode以一个消息和一棵树为参数，产生出被编码消息所对应的二进制位的表：

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


(define (encode-symbol char tree)
(let
(
(left (left-branch tree))
(right (right-branch tree))
)
(if (leaf? left)
(if (eq? (symbol-leaf left) char)
(list '0)
(if (leaf? right)
(if (eq? (symbol-leaf right) char)
(list '1)
'error-not-found-in-tree
)
(let
(
(right-res (encode-symbol char right))
)
(if
(eq?
right-res
'error-not-found-in-tree
)
'error-not-found-in-tree
(append (list '1) (encode-symbol char right))
)
)
)
)
(
(let
(
(left-res (encode-symbol char left))
)
(if (eq? (left-res 'error-not-found-in-tree))
(encode-symbol char right)
left-res
)
)
)
)
)
)


decode 的代码如下：

(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 (left-branch tree) (car 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-message '(0 1 1 0 0 1 0 1 0 1 1 1 0))

(decode sample-message sample-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)
)
)
)
)

(encode-symbol 'A sample-tree)

(encode (list 'A 'D 'A 'B 'B 'C 'A) sample-tree)