Baumfalte im Schläger

Oct 23 2020

Ich bin ein Anfänger bei Racket und habe folgende Frage:

definiert eine Struktur node, die die folgenden Felder hat: value, left, middle, right. Diese Struktur repräsentiert Knoten in einer Baumstruktur.
Diese Felder enthalten den im Knoten gespeicherten Wert, den linken Teilbaum, den mittleren Teilbaum bzw. den rechten Teilbaum. Wenn kein Teilbaum vorhanden ist, sollte das entsprechende Feld einen emptyNodewie unten beschrieben enthalten .

Definieren Sie eine Struktur, emptyNodeum einen leeren Knoten im Baum anzugeben.

Schreiben Sie eine Funktion, treeFolddie eine Funktion, feinen Anfangswert initialund eine Baumstruktur treeals Parameter verwendet. Es sollte dann einen einzelnen Wert erzeugen , das ist das Ergebnis der Verwendung fder Werte im Baum (mit falten left, middleund rightTeilbäumen in dieser Reihenfolge). Beachten Sie, dass dies feine Funktion ist, die zwei Parameter akzeptiert. Der erste Parameter ist ein Wert aus dem Baum und der zweite ist das teilweise akkumulierte Ergebnis.

Der Funktionsaufruf sollte lauten:

(treeFold (lambda (a acc) (+ a acc)) 15 tree)

Baum:

(node 7 (node 5 (emptyNode) (emptyNode) (emptyNode)) 
        (node 20 (emptyNode) (emptyNode) (emptyNode)) 
        (emptyNode))

die Ausgabe : 47

das habe ich bisher gemacht:

(struct node (value left middle right) #:transparent)

(struct emptyNode () #:transparent)

(define tree 
    (node 7 
          (node 5 (emptyNode) (emptyNode) (emptyNode)) 
          (node 20 (emptyNode) (emptyNode) (emptyNode)) 
          (emptyNode)))

(define (treeFold f initial tree)
  (if (emptyNode? tree)
     (emptyNode)
     (node (f initial (node-value tree))
           (node-left tree)
           (node-middle tree)
           (node-right tree))))

Wie kann ich die Gesamtheit der gesamten Blätter erhalten?

Irgendwelche Ideen oder Hilfe, danke

edit: also, basierend auf der Antwort und Diskussion in den Kommentaren, habe ich eine neue Funktion bekommen, aber es gibt immer noch einen Fehler und ich konnte ihn nicht finden. hier ist es:

(define (treeFold f initial tree) 
  (cond 
    [(emptyNode? tree) 
          (f initial 0)] 
    [else (f (node-value tree) 
             (f (treeFold f 
                   (treeFold f 
                      (treeFold f initial 
                         (node-left tree)) 
                      (node-middle tree)) 
                    (node-right tree))))]))

Könnten Sie mir bitte sagen, wie ich das Problem beheben kann? Dankeschön.

bearbeiten: endgültiger Code

(define (treeFold f initial tree) 
  (cond 
    [(emptyNode? tree) (f initial 0)] 
    [else (f  (node-value tree)                
              (treeFold f                   
                   (treeFold f 
                        (treeFold f initial 
                             (node-left tree)) 
                             (node-middle tree)) 
                             (node-right tree)))]))

es funktioniert wie ich erwartet hatte

Antworten

WillNess Oct 24 2020 at 11:37

Update nach Frage wurde mit neuer Version der Funktion bearbeitet.

Es ist ein Schritt in die richtige Richtung. Es gibt einige richtige Teile und einige falsche Teile.

Funktionen sind wie Boxen, die miteinander verdrahtet werden können. Sachen gehen an einigen Drähten rein und an anderen raus. Jede Box hat die richtige Art der Verwendung: die Anzahl der Drähte und das Material, in das sie fließen soll.

Ihre neue Version:

(define (treeFold f initial tree) 
  (cond 
    [(emptyNode? tree) 
          (f initial 0)] 
    [else (f (node-value tree)                 ;; (1)
             (f (treeFold f                    ;; (2)
                   (treeFold f 
                      (treeFold f initial 
                         (node-left tree)) 
                      (node-middle tree)) 
                    (node-right tree))))]))

ferwartet zwei Argumente. (f initial 0) sieht zumindest in dieser Hinsicht richtig aus. Der Anruf (1)auch. Aber der Aufruf von fat (2)hat nur ein Argument f, kann also nicht richtig sein.

Weiter zur Bedeutung. Die drei verschachtelten Aufrufe von treeFoldsind fast richtig: Wir "gehen hinein" (node-left tree), dh in den linken Unterbaum, mit initialals Anfangswert, dann erhalten wir das Ergebnis daraus und verwenden es als neuen Anfangswert, um in das mittlere Unterbaum zu gelangen -tree und verwende das berechnete Ergebnis, um über den rechten Unterbaum zu gehen. Nett. Wir sind fertig . Das ist das endgültige Ergebnis , das wir brauchen - keine Notwendigkeit , es zu füttern fjeden weiteren. Diese beiden Aufrufe füber den drei verschachtelten Aufrufen treeFoldwerden also überhaupt nicht benötigt.

Außer, was sollen wir mit dem machen (node-value tree)? Wo passt es hin? Die Antwort ist, sollte es mit dem kombiniert wird initialWert, haft Aufruf f, und das Ergebnis der , dass sollte als Anfangswert verwendet werden , mit dem wir denen gehen über linken Unterbaum; der Wert , mit dem wir beginnen die Faltung.

Der Basisfall ist ebenfalls falsch. Wir haben bereits das initial, warum sollten wir es 0plötzlich mit kombinieren müssen ? Und warum 0? Wir könnten zum Beispiel einen Baum falten, der Strings enthält , und das Kombinieren von Strings mit einer Zahl 0würde nicht viel Sinn machen.