CPSed二叉树遍历不像预期的那样工作

Question

我的递归版本看起来像

(struct node (val left right) #:transparent)

(define t3 (node 3 '() '()))
(define t4 (node 4 '() '()))
(define t5 (node 5 '() '()))
(define t2 (node 2 t4 t5))
(define t1 (node 1 t2 t3))
;
;     ----- 1 -----
;    |             |
; -- 2 --          3
;|       |
;4       5

(define (countv tree)
  (if (null? tree)
      0
      (+ (node-val tree)
         (countv (node-left tree))
         (countv (node-right tree)))))

(countv t1)

和CPSed版本

(define (countk tree k)
  (if (null? tree)
      (k 0)
      (countk (node-left tree)
              (λ (lval)
                (countk (node-right tree)
                        (λ (rval)
                          (+ (node-val tree) lval rval)))))))

(countk t1 (λ (x) (node-val x)))

countv的结果如预期的15，countk则得到4。

Answer 1

您忘记将递归结果传递给延续：

(define (countk tree k)
  (if (null? tree)
      (k 0)
      (countk (node-left tree)
              (λ (lval)
                (countk (node-right tree)
                        (λ (rval)
                          (k (+ (node-val tree) lval rval))))))))
                           ^
                          Here

记住这一点之后，您将得到一个运行时错误，因为结果不是树。

这在您的代码中没有发生，因为您的初始延续从未应用于任何东西。

你应该这样称呼它：

(countk t1 (λ (x) x))