algorithm - 方案中的后序遍历

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

我检查了 append 和 cons 的语法。我仍然无法弄清楚这个问题。似乎逻辑而不是语法有问题。

能不能指出来解释一下。谢谢你。

Answer 1

带有append参数的是列表。在您的代码中，您将添加head作为虚线值，因此该列表只能在连续的最后一个参数中使用append。这将解决它：

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