scheme - 方案树图

Question

编写 n 个类似函数(maptree f t)，返回通过将函数f应用于二叉树的每个条目而生成的树t。（就像map）由于树是一种数据抽象，所以只允许对树进行以下操作：(entry t) (right-branch t) （left-branch t) (make=tree entry left right), and (empty-tree? t). 您可以使用预定义的常量the-empty-tree。

例子：

(define tree 
(make-tree 10 (make-tree 5 the-empty-tree the-empty-tree)
          (make-tree 12 the-empty-tree the-empty-tree)))


tree

(10 (5 () ())(12 () ()))

(maptree square tree)

(100 (25 () ())(144 () ()))

Answer 1

像这样：

(define (maptree func tree)
  (if (empty-tree? tree)
      the-empty-tree
      (make-tree (func (entry tree))
                 (maptree func (left-branch  tree)) 
                 (maptree func (right-branch tree)))))

当递归定义数据结构时，函数的实现可能自然是递归的。在这种情况下，对一个树项执行该函数，然后在左右子树上递归。

Answer 2

这似乎是一个家庭作业问题。一个好的起点是在重建树的同时递归地沿着树向下走。检查左右是否为空，如果没有，则在每个分支上再次调用您的 map 函数。

从顶部（第一个entry）开始，创建一棵新树，f应用函数entry并检查左右分支是否the-empty-tree存在。如果没有，请在每个分支上再次调用该函数。