Übung 310. "Wie man Programme entwickelt"

Question

Ich würde eine Hand mit dieser Übung schätzen. Aufgabe 310. Entwerfen Sie die Funktion inorder. Es konsumiert einen Binärbaum und erzeugt die Sequenz aller ssn-Zahlen im Baum, wenn sie von links nach rechts auftauchen, wenn sie eine Baumzeichnung betrachten.

Meine Lösung kehrt einfach jeden linken Knoten um, was unterhalb des Knotens ist, und greift dann auf den rechten Knoten zu. Obwohl die Reihenfolge korrekt ist, ist die Antwort nicht im richtigen Format. Dies ist mein Code:

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

Dies ist das Ergebnis, wenn ich (inorder six3) (Liste (Liste (Liste (Liste '() 10) 15'() 24) 29) 63 (Liste ‚() 77) laufen 89 '() 95'() 99)

Answer 1

Es gibt viele seltsame Elemente in Ihrem Code. Ich erwarte inorder würde eine Liste zurückgeben, aber immer noch packen Sie das Ergebnis in einer Liste (list (inorder (node-left bt)) vor dem consing. Es ist der einzige Grund, warum Sie eine Reihe von verschachtelten Listen erhalten.

Warum das Gegenteil? Jedes Level im Baum endet mit einer Teilliste, die du umkehrst. Die Reihenfolge wird dann bestimmt, ob der Baum eine ungerade oder gerade Höhe aufweist.

Da inorder Rekursion tatsächlich gibt (10 15 24 29) und (77 89 95 99) Sie (append (reverse (cons 63 (list '(10 15 24 29)))) '(10 15 24 29)) tun, die in ((10 15 24 29) 63 77 89 95 99) führen würde, aber natürlich auch die Rekursion Rückkehr nicht wirklich diese Listen, da es auch eine verschachtelte Liste machen usw.

Wenn Sie zwei Listen und ein Element, und Sie müssen, dass ein Element in der Mitte sein, was Sie tun (append (10 15 24 29) (list 63) (77 89 95 99))

Jetzt ein viel besserer Weg, dies zu tun gibt es:

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

Bevor eine Prozedur angewendet werden kann, müssen die Argumente berechnet werden, so dass (tree->list (node-right tree) acc) zuerst ausgeführt wird. Es wird (77 89 95 99) für Ihren Baum haben und es wird '() für einen Knoten mit einem ssn mit zwei Nullknoten sein. Dann ist die ssn auf der rechten Seite konsoliert. Dann wird es als Akkumulator für die Rekursion auf der linken Seite fungieren.

Da eine Liste mit cons vom Ende bis zum Anfang gemacht wird, ist dies die Reihenfolge, in der das Verfahren läuft, so dass append``and certainly no need for reverse nicht benötigt wird.

Answer 2

Nach etwas zu lesen tun kam ich mit auf dem Punkt:

; 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)))])) 

Nicht so elegant mit der einem Begriff Liste. Es funktioniert jedoch gut.

Oder diese:

; 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))]))