data-structures - 将函数应用于 Racket 中的树结构

Question

我正在尝试以 Map 的形式将函数应用于一棵树，但不确定如何准确地进行操作。这是我的尝试..

    (define-struct node (value left middle right)#:transparent)

(struct emptyNode () #:transparent) ; leaf node

(define T (node 1 (node 2 (node 5 (emptyNode) (emptyNode) (emptyNode)) (emptyNode) (emptyNode))
                            (node 3 (emptyNode) (node 6 (emptyNode) (node 8 (emptyNode) (emptyNode) (emptyNode)) (emptyNode)) (emptyNode))
                            (node 4 (emptyNode) (emptyNode) (node 7 (emptyNode) (emptyNode) (emptyNode)))))

;                   1
;                 / |  \
;               2   3   4
;              /    |     \
;             5     6      7
;                   |
;                   8

;f
;   a function, f, used in MaptoTree
(define (f b)
  (* b 2))

;MaptoTree
;    takes a function, f, and a tree structure, tree, as parameters.
;    it should then produce a new tree structure where f has been applied to each value in the original tree
(define (MaptoTree f T)
  (if (pair? T)
      ((map (lambda (x) (MaptoTree f x)) (rest T)))
      (f T)))

编辑:删除了关于将结构转换为列表的问题

Answer 1

您必须使用 node 的选择器, 而不是 pair? , rest等。我们正在使用 struct表示树，而不是普通列表。

解决这个问题后，我们只需要遍历树，对每个值应用该函数，边走边构建一棵新树 - 像这样:

(define (MaptoTree f T)
  (if (emptyNode? T)
      (emptyNode)
      (node (f (node-value T))
            (MaptoTree f (node-left T))
            (MaptoTree f (node-middle T))
            (MaptoTree f (node-right T)))))