将虚线对合并到huffman树中

Question

我有一个称为make-leaf-set的过程，该过程创建叶节点和另一个过程，该过程将最低的first-high排序。

(define (make-leaf-set pairs) 
    (if (null? pairs) 
    '() 
    (let ((pair (car pairs))) 
     (adjoin-set (make-leaf (car pair) 
          (cdr pair)) 
       (make-leaf-set (cdr pairs)))))) 


(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)))))) 


"Predefined dotted paires" 
(define pairs '((a . 2) (b . 5) (c . 1) (d . 3) (e . 1) (f . 3))) 
=> ((leaf e 1) (leaf c 1) (leaf a 2) (leaf f 3) (leaf d 3) (leaf b 5)) 

对在使用时可以很好地工作（制作叶组对）。一切都是排序的。 我也用这就叫make码树

(define (make-code-tree left right) 
    (list left 
     right 
    (append (symbols left) (symbols right)) 
    (+ (weight left) (weight right)))) 

(define (symbols tree) 
    (if (leaf? tree) 
    (list (symbol-leaf tree)) 
    (caddr tree))) 

(define (weight tree) 
    (if (leaf? tree) 
    (weight-leaf tree) 
    (cadddr tree))) 

• 的目标是创造这需要对列表，然后创建一个哈夫曼树的过程另一个程序。

作为开始我COMED了这个

(define (grow-huffman-tree list) 
    (successive-merge (make-leaf-set list) '())) 

(define (successive-merge par tree) 
    (if (null? par) 
     tree 
    (append (make-code-tree (car par) (cadr par)) tree))) 

因为它位于它合并两个第一元件和给出（（叶ë1）（叶的C 1）（EC）2） 。 但我希望它合并所有树叶，使它像huffman-tree一样构建，并且我无法设法将其他树叶合并到此树中。我试图调用（连续合并（cdr par）树）将导致元素d 3上的错误...

Answer 1

我建议您从较小的初始示例开始，并计算出什么grow-huffman-tree（也许是successive-merge ，这取决于这是否真的是一个适当的帮手程序）对每个小例子都有效。

例如，我有一个很难相信，这条线在successive-merge：

(append (make-code-tree (car par) (cadr par)) tree) 

都不可能使任何意义。 （但是，如果没有数据定义tree，其中包括应该如何解释类​​的实例，那么很难说什么是无意义的，什么是“聪明的”。

请记住，单词“Tree “在‘​​霍夫曼树’颇为相关，您不想建立一个Listof X;你而是想将Treeof X.所以，如果你看到正在打印出像数据：

((obj 1 2) (obj 3 4) (obj 5 6) ... (obj 100 101)) 

即不是通常被看作是一棵有趣的树;更常被认为是一个列表（严格地说，它可以是inte诠释为一棵树;只是很浅的树，一个非常大的分支因子）

树结构最终将打印是这样的一个更常见的例子：

(node a 1 (node b 2 (leaf 17) 
        (node d (leaf 26) 
          (leaf 17))) 
      (node c 6 (leaf 18) 
        (leaf 1)))