2.3.4实例哈夫曼编码树

哈夫曼树用于给字符编码，其中哈夫曼树方法能够对于同样的信息谁用更少（或者说最少）的二进制位。其算法具体思想不作赘述，主要在于代码的实现

#lang sicp
;;首先思考如何表示树和叶
  ;;以下是叶子的表示
(define (make-leaf symbol weight);;构造一个叶子
  (list 'leaf symbol weight)
  )
(define (leaf? object);;判断是否是叶子
  (eq? (car object)
       'leaf))
(define (symbol-leaf leaf);;选择出叶子的符号集合
  (cadr leaf)
  )
(define (weight-leaf leaf);;选择出叶子的权重
  (caddr leaf)
  )
;;以下是树的表示
(define (append list1 list2);;这个方法用递归求两个节点符号集合的并集，下面要用
  (if (null? list1)
      list2
      (cons (car list1) (append (cdr list1) list2))))

(define (make-code-tree left right);;构造一个编码树
  (list left
        right
        (append (symbols left) (symbols right))
        (+ (weight left) (weight right)))
  )
(define (left-branch tree);;选择出左子树
  (car tree))
(define (right-branch tree);;选择出右子树
  (cadr tree))
(define (symbols tree);;选择出节点集合
  (if (leaf? tree)
      (symbol-leaf tree);;这里与书上不同
      (caddr tree)))

(define (weight tree);;选择出节点权重
  (if (leaf? tree)
      (weight-leaf tree)
      (cadddr tree)))
;;下面构造解码过程
(define (decode bits tree)
  (define (decode-recur 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-recur (cdr bits) tree))
                  (decode-recur (cdr bits) next-branch)))))
    (decode-recur bits tree))

(define (choose-branch bit branch);;用来选择下一个分支
  (cond ((= bit 0) (left-branch branch))
        ((= bit 1) (right-branch branch))
        (else (error "bad bit"))
        ))
;;用来把一个节点加入集合;;默认序对是增序的
(define (adjoin-set x set)
  (cond ((null? set) (list x))
        ((< (weight x) (weight (car set))) (cons x set))
        (else (cons (car set (adjoin-set x (cdr set)))))))

(define (make-leaf-tree pairs);;构造一个叶子的初始排序集合。这里默认序对是增序的
  (if (null? pairs)
      '()
      (let ((pair (car pairs)))
        (adjoin-set (make-leaf (car pair)
                               (cadr pair))
                    (make-leaf-tree (cdr pairs))))))
(make-leaf-tree '((A 6)));;测试实例