Nachtragstraverse im Schema

Question

Ich arbeite an Post Order Traversal zu einem binären Suchbaum. Das ist, was ich bis jetzt habe

(define (head tree) 
    (car tree)) 
(define (left tree) 
    (cadr tree)) 
(define (right tree) 
    (caddr tree)) 

    (define (post-order node) 
    (if (null? node) 
      '() 
      (append (cons (post-order (left node)) 
      (post-order (right node))) 
      (head node)))) 

Ich erwarte, dass dieser Code eine Liste der Post-Auftragstraverse zurückgeben kann. Allerdings kompiliert es nicht einmal. Der Fehler ist

mcar: contract violation 
    expected: mpair? 
    given: 5 

ich die Syntax der append und Nachteile überprüft haben. Und ich kann dieses Problem immer noch nicht lösen. Es scheint, dass etwas mit der Logik und nicht mit der Syntax falsch ist.

Können Sie darauf hinweisen und es erklären. Vielen Dank.

Answer 1

Mit append sind die Argumente Listen. In Ihrem Code fügen Sie den head als den punktierten Wert hinzu und folglich kann diese Liste nur das letzte Argument in fortlaufenden append blenden. Dies würde es beheben:

(define (post-order node) 
    (if (null? node) 
     '() 
     (append (post-order (left node)) 
       (post-order (right node)) 
       (list (head node)))))