Chapter 2, Building Abstractions with Data
Section - 2.3 Symbolic Data
Exercise 2.69
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(define (successive-merge pairs)
(if (null? (cdr pairs))
(car pairs)
(let (
(first (car pairs))
(second (cadr pairs))
)
(successive-merge (adjoin-set
(make-code-tree first second)
(cddr pairs)
)
)
)
)
)
Test/Output
1
2
3
4
5
6
7
8
9
10
> (define pairs '((A 4) (B 2) (C 1) (D 1)))
> (define tree (generate-huffman-tree pairs))
> (display tree)
((leaf A 4) ((leaf B 2) ((leaf D 1) (leaf C 1) (D C) 2) (B D C) 4) (A B D C) 8)
> (display sample-tree)
((leaf A 4) ((leaf B 2) ((leaf D 1) (leaf C 1) (D C) 2) (B D C) 4) (A B D C) 8)
> (define encoded-msg (encode '(A D A B B C A) tree))
> (display encoded-msg)
(0 1 1 0 0 1 0 1 0 1 1 1 0)
>