Racket Inorder (Baum) kehrt Liste

Question

Ich habe ein Inorder Funktion wie folgt aus:

(define inorder 
    (λ (tree) 
      (unless(empty? (node-left tree)) (inorder(node-left tree))) 
      (print (node-x tree)) 
      (unless(empty? (node-right tree)) (inorder(node-right tree))) 
) 
) 

Wie kann ich eine Liste mit allen Knoten-x Baumelemente anstelle des Druckens sie erstellen. Ich brauche meine Inorder-Funktion, um eine Liste dieser Elemente zurückzugeben. Ich habe versucht, eine Hilfsfunktion, aber es hat nicht funktioniert ...

Answer 1

Der erste Schritt ist inorder erhalten, um eine Liste zurückzugeben. Angenommen, Sie möchten eine flache Liste, bedeutet dies, dass wir die Liste von inorder für den linken Teilbaum, den aktuellen Knoten und den rechten Teilbaum nehmen und jede Liste davon anhängen können, um eine flache Liste von Knoten zu erzeugen Werte von ganz links von Ihrem Binärbaum auf der rechten Seite.

(define inorder 
    (λ (tree) 
    (append (inorder(node-left tree)) 
      (list (node-x tree)) 
      (inorder(node-right tree))))) 

Beachten Sie, dass ich eine Liste der Länge 1 für den aktuellen Knoten erstellen, während die Unterbäume Listen zurückgeben werden. Dieses Skelett sollte ausreichen, um den Kopf darüber zu führen, wie Rekursion dieses Problem lösen wird.

Jetzt für den Fall, wo wir einen leeren Baum bekommen: Wenn wir einen leeren Baum haben, dann sollten wir eine leere Liste zurückgeben, da es keine Elemente zum Hinzufügen gibt. Dies ist einfach zu tun mit if:

(define inorder 
    (λ (tree) 
    (if (empty? tree) 
     '() 
     (append (inorder(node-left tree)) 
       (list (node-x tree)) 
       (inorder(node-right tree)))))) 

Answer 2

Sie müssen sich vorstellen, dass (inorder (node-left tree)) und (inorder (node-right tree)) sowohl eine Liste zurück. Wie nimmst du diese und dieses Element, um das Endergebnis zu erzielen?

Das Ergebnis für einen leeren Baum wäre eine leere Liste. Das sollte Ihr Basisfall sein:

So müssen Sie es so etwas wie folgt aussehen:

(define (inorder tree) 
    (if (empty? tree) 
     '() 
     (append (inorder (node-left tree)) 
       (list (node-x tree)) 
       (inorder (node-right tree))))) 

Eine viel bessere Version, die nicht append für jede Ebene nicht verwendet, sondern legt die Elemente in es korrekt ist Position einmal für jedes Element ist das:

Etwas schwerer zu verstehen, aber es funktioniert auf größeren Bäumen besser.