スキームのポストオーダートラバース

Question

私はバイナリ検索ツリーへのポストオーダートラバーサルに取り組んでいます。これは私がこれまで

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

私はこのコードはポストオーダートラバースのリストを返すことができ期待しなければならないものです。しかし、それはコンパイルされません。 エラーは、私が追記両論の構文をチェックして

mcar: contract violation 
    expected: mpair? 
    given: 5 

です。そして、私はまだこの問題を理解することはできません。構文よりもロジックに何か問題があるようです。

あなたはそれを指摘し説明することができますか？ありがとうございました。

Answer 1

appendの場合、引数はリストです。あなたのコードでは、headをドット付きの値として追加しています。したがって、このリストは最後の引数をのあいだにのみ引き出すことができます。これで修正されます：

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