1 (define (make-leaf symbol weight)
2   (list 'leaf symbol weight))
3 (define (leaf? object)
4   (eq? (car object) 'leaf))
5 (define (symbol-leaf x) (cadr x))
6 (define (weight-leaf x) (caddr x))
7 
8 (define (make-code-tree left right)
9   (list left
10 	right
11 	(append (symbols left) (symbols right))
12 	(+ (weight left) (weight right))))
13 
14 (define (left-branch tree) (car tree))
15 (define (right-branch tree) (cadr tree))
16 (define (symbols tree)
17   (if (leaf? tree)
18       (list (symbol-leaf tree))
19       (caddr tree)))
20 (define (weight tree)
21   (if (leaf? tree)
22       (weight-leaf tree)
23       (cadddr tree)))
24 
25 (define (decode bits tree)
26   (define (decode-1 bits branch)
27     (cond ((if (and (null? bits)
28 		    (leaf? branch))
29 	       (list (symbol-leaf branch))
30 	  ;; ((null? branch) 
31 	  ;;  ("error: symbol not found"))
32 	  ((leaf? branch) 
33 	   (cons (symbol-leaf branch)
34 		 (decode-1 (cdr bits) 
35 			   (choose-branch (car bits) tree))))
36 	  (else (decode-1 (cdr bits) 
37 			  (choose-branch (car bits) branch)))))
38   (decode-1 bits tree))
39 
40 
41 
42 
43 
44 
45 
46 
47 
48 
49 
50 
51 
52 
53 
54 
55 
56 
57 
58 
59 
60 
61 
62 
63 
64 
65 
66 
67 
68 
69 
70 
71 
72 
73 
74 
75 
76 
77 
78 
79 
80 
81 
82 
83 
84 
85 
86 
87 (define (decode bits tree)
88   (define (decode-1 bits current-branch)
89     (if (null? bits)
90 	'()
91 	(let ((next-branch
92 	       (choose-branch (car bits) current-branch)))
93 	  (if (leaf? next-branch)
94 	      (cons (symbol-leaf next-branch)
95 		    (decode-1 (cdr bits) tree))
96 	      (decode-1 (cdr bits) next-branch)))))
97   (decode-1 bits tree))
98 (define (choose-branch bit branch)
99   (cond ((= bit 0) (left-branch branch))
100 	((= bit 1) (right-branch branch))
101 	(else (error "bad bit -- CHOOSE-BRANCH" bit))))