問題2.68

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


;; rec
(define (encode-symbol message tree)
  (if (leaf? tree)
      '()
      (if (memq message (symbols (left-branch tree)))
          (cons 0 (encode-symbol message (left-branch tree)))
          (cons 1 (encode-symbol message (right-branch tree))))))

;; trec
(define (encode-symbol message tree)
  (define (iter m t bits)
    (if (leaf? t)
        (reverse bits)
        (if (memq m (symbols (left-branch t)))
            (iter m (left-branch t) (cons 0 bits))
            (iter m (right-branch t) (cons 1 bits)))))
  (iter message tree '()))


(let ((msg '(A D A B B C A)))
  (equal? msg (decode (encode msg sample-tree) sample-tree)))

;=> #t
; ok