練習310.「如何設計程序」

Question

我會很感激這個練習。 練習310.按順序設計功能。它消耗一棵二叉樹，併產生樹中所有ssn數字的序列，因爲它們在查看樹圖時從左到右顯示。

我的解決方案只是將每個左節點與節點下的節點顛倒過來，然後訪問正確的節點。雖然順序是正確的，但答案並不是正確的格式。這是我的代碼：

(define-struct no-info []) 
(define NONE (make-no-info)) 

(define-struct node [ssn name left right]) 
; A BinaryTree (short: BT) is one of: 
; – NONE 
; – (make-node Number Symbol BT BT) 

(define nine9 (make-node 99 "nine9" NONE NONE)) 
(define one0 (make-node 10 "one0" NONE NONE)) 
(define two4 (make-node 24 "two4" NONE NONE)) 
(define one5 (make-node 15 "one5" one0 two4)) 
(define seven7 (make-node 77 "seven7" NONE NONE)) 
(define nine5 (make-node 95 "nine5" NONE nine9)) 
(define two9 (make-node 29 "two9" one5 one8)) 
(define eight9 (make-node 89 "eight9" seven7 nine5)) 
(define six3 (make-node 63 "six3" two9 eight9)) 

; BT -> list 
; produce the sequence of ssn numbers from left to right 
(define (inorder bt) 
    (cond 
    [(no-info? bt) '()] 
    [else (append (reverse (cons (node-ssn bt) (list (inorder (node-left bt))))) 
        (inorder (node-right bt)))])) 

這是結果，當我運行(inorder six3) （名單（名單（名單（名單 '（）10）15'（）24）29）63（名單「（）77） 89'（）95'（）99）

Answer 1

代碼中有很多奇怪的元素。我希望inorder會返回一個列表，但你仍然在包裝結果列表(list (inorder (node-left bt))收購之前。這是你得到一堆嵌套列表的唯一原因。

爲什麼相反？樹中的每個關卡最後都會出現一個反向的部分列表。然後確定樹的高度是奇數還是偶數。

鑑於inorder遞歸實際上返回(10 15 24 29)和(77 89 95 99)你做(append (reverse (cons 63 (list '(10 15 24 29)))) '(10 15 24 29))這將導致((10 15 24 29) 63 77 89 95 99)但當然遞歸真的不歸還這些名單，因爲它也將使嵌套列表等

如果你有兩個列表和一個元素，你需要的是一個元件是在你做(append (10 15 24 29) (list 63) (77 89 95 99))

中間現在有一個更好的方法來做到這一點：

(define (tree->list tree (acc '())) 
    (if (tree-null? tree) 
     acc 
     (tree->list (node-left tree) 
        (cons (node-ssn tree) 
         (tree->list (node-right tree) acc))))) 

在可以應用程序之前，需要計算參數，因此首先完成(tree->list (node-right tree) acc)。對於你的樹，它將有(77 89 95 99)，對於一個有兩個空節點的ssn的節點，它將是'()。然後ssn被置於右側。然後它將充當左側遞歸的累加器。

由於從頭到尾使用cons作爲該過程執行的順序，因此不需要append``and certainly no need for反轉。

Answer 2

做一些閱讀後，我想出了這個：

; BT -> list 
; produce the sequence of ssn numbers from left to right 
(define (inorder bt) 
    (cond 
    [(no-info? bt) '()] 
    [else (append (inorder (node-left bt)) (list (node-ssn bt)) 
        (inorder (node-right bt)))])) 

用一個術語列表不那麼優雅。但它運作良好。

或者這樣：

; BT -> list 
; produce the sequence of ssn numbers from left to right 
(define (inorder bt) 
    (cond 
    [(no-info? bt) '()] 
    [else (append (add-to-end (inorder (node-left bt)) (node-ssn bt)) 
        (inorder (node-right bt)))])) 

(define (add-to-end ls ssn) 
    (cond 
    [(empty? ls) (cons ssn '())] 
    [else (cons (first ls) (add-to-end (rest ls) ssn))]))