使用折叠在树中平方数

Question

目的是使用折叠树函数生成一棵包含所有数字平方的树。顺便说一句，这不是家庭作业。这样我就可以自由讨论了。

; A Tree-Of-Numbers is one of:
; - (make-node Tree-Of-Numbers Number Tree-Of-Numbers)
; - EmptyTree
; interp. a tree with numbers stored at its nodes.

(define-struct node (left value right))

; An EmptyTree is a structure (make-empty-tree))
; interp. an empty tree

(define-struct empty-tree ())

(define EXAMPLE-TREE
  (make-node (make-node (make-node EMPTY 6 EMPTY)
                        20 EMPTY) 8 (make-node (make-node EMPTY 14 EMPTY)
                        42 (make-node EMPTY 2 EMPTY))))

(define EMPTY (make-empty-tree))

我编写了一个折叠树函数：


(define (fold-tree f b tree)
  (cond
    [(empty-tree? tree) b]
    [else (f (node-value tree)
             (fold-tree f b (node-left tree))
              (fold-tree f b (node-right tree)))]))

现在我必须使用这个函数来计算树中所有数字的平方。我可以通过其他方式做到这一点，例如：

(define (sqr-tree tree)
  (cond
    [(empty-tree? tree) EMPTY]
    [(node? tree) (make-node (sqr-tree (node-left tree))
                                 (sqr (node-value tree))
                                 (sqr-tree (branch-right tree)))]))

我还可以通过编写映射树函数并使用它对树中的所有数字进行平方来做到这一点。但问题是，如何使用折叠树来做到这一点？

Answer 1

假设所有帮助程序都是正确的，这应该有效：

(define (sqr-tree tree)
  (fold-tree (lambda (value left right)
               (make-node left (sqr value) right))
             EMPTY
             tree))

使用折叠在树中平方数

square numbers in a tree using fold

binary-search-tree

racket

fold