在Scheme中获取树中元素的总和

Question

编写一个过程(fold-right-tree op id tree)，该过程使用op将树的叶子聚集在一起，类似于在列表上向右折叠。因此，如果树具有价值

(((1 2)
  3)
 (4
  (5 6))
 7
 (8 9 10))

然后

(fold-right-tree + 0  tree)

具有值55。

-我想定义对树中所有元素求和的代码

 ;;----------

    (#%require racket)
    (define nil empty) 


    (define (reduce op init lst)
      (if (null? lst)
          init
          (op (car lst)
              (reduce op init (cdr lst)))))

    (define fold-right reduce)


    (define (sum-list lst)
      (if (null? lst) 0
          (+ (car lst) (sum-list (cdr lst)))
        ))

(define (leaf? x)
  (not (pair? x)))


    (define (fold-right-tree op init tree)
        (lambda (tree)
          (if (null? tree)
              0
              (if (leaf? tree)
                  (sum-list (list tree))
                  (fold-right op init (map fold-right-tree op init tree))))))


    (fold-right-tree (lambda (x,y) (+ x y)) 0 '((1) (2 3 4) (((5)))) )

输出应返回树元素的总和，但是返回#<procedure>

我的问题是什么？

我也尝试过这个，但是这次我遇到了映射错误

(define (fold-right-tree op init tree)
      (if (null? tree)
          0
          (if (leaf? tree)
              (fold-right op init (list tree))
              (+ (fold-right-tree op init (map car tree)) (fold-right-tree op init (map cdr tree))))))


(fold-right-tree sum 0 '((1) (2 3 4) (((5)))) )

Answer 1

从问题说明中，您可以简单地获取树的所有叶子（使用flatten函数），然后应用相关的折叠操作，例如：

(define (fold-right-tree op id tree)
  (foldr op id (flatten tree)))

(fold-right-tree + 0 '((1) (2 3 4) (((5)))))  ; => 15

这已在Dr.Racket中测试过。

Answer 2

[使用适当的树访问器和谓词（leaf?，empty-tree?，left-subtree和right-subtree），则显而易见的定义是：

(define (fold-right-tree op accum tree)
  (cond
    [(empty-tree? tree)
     accum]
    [(leaf? tree)
     (op accum tree)]
    [else (fold-right-tree op
                           (fold-right-tree op accum (right-subtree tree))
                           (left-subtree tree))]))

这具有完全不了解树表示的优点：它只知道访问器的名称。确实，您可以将其设为really不可知的：

(define (fold-right-tree op init tree
                         #:empty-tree? (empty? empty-tree?)
                         #:leaf? (lief? leaf?)
                         #:left-subtree (left left-subtree)
                         #:right-subtree (right right-subtree))
  (let frt ([a init] [t tree])
    (cond
      [(empty? t) a]
      [(lief? t) (op a t)]
      [else (frt (frt a (right t)) (left t))])))

现在它将遍历任何类型的二叉树。