將虛線對合併到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)))