Post 方案中的顺序遍历

Question

我正在研究 post 二叉搜索树的顺序遍历。这是我目前所拥有的

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

我希望这段代码可以return一个post顺序的列表遍历。但是它甚至不编译。错误是

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

Post 方案中的顺序遍历

Post order traverse in scheme

algorithm

tree

scheme

r5rs

postorder