Serendip

Web Studio

問題2.68

記号が木に存在するかどうかを調べるには、ルートにある記号の集合のリストを最初に調べるとよい。
左部分木に記号が存在すれば左部分木をたどって行き、左部分木に無い場合は右部分木をたどって行く。

(define (encode-symbol symbol tree)
  (define (enc-iter tree)
    (if (leaf? tree)
        '()
        (if (memq symbol (symbols (left-branch tree)))
            (cons 0 (enc-iter (left-branch tree)))
            (cons 1 (enc-iter (right-branch tree))))))
  (if (memq symbol (symbols tree))
      (enc-iter tree)
      (error "Not Found symbol of " symbol)))

(define (encode message tree)
  (if (null? message)
      '()
      (append (encode-symbol (car message) tree)
              (encode (cdr message) 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)))))
; ((leaf A 4) ((leaf B 2) ((leaf D 1) (leaf C 1) (D C) 2) (B D C) 4) (A B D C) 8)

(encode '(A D A B B C A) sample-tree)
gosh> (0 1 1 0 0 1 0 1 0 1 1 1 0)
(encode '(A D A F B C A) sample-tree)
gosh> *** ERROR: Not Found symbol of  F
Stack Trace:
_______________________________________
  0  (encode-symbol (car message) tree)
        At line 28 of "(stdin)"
  1  (encode (cdr message) tree)
        At line 29 of "(stdin)"
  2  (encode (cdr message) tree)
        At line 29 of "(stdin)"
  3  (encode (cdr message) tree)
        At line 29 of "(stdin)"

計算機プログラムの構造と解釈

posted with amazlet at 08.11.07

ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542

Amazon.co.jp で詳細を見る