使用数据类型和递归在方案中制作列表列表

Question

我目前正在学习Scheme，刚刚学习了归纳集和递归。我目前定义了一个数据类型 bTree，它是一个二叉树

(define-datatype bTree bTree?
  (leaf
    (datum number?))
  (node
    (value symbol?)
    (left bTree?)
    (right bTree?)))

效果很好。我想创建一个函数，当给定一个 bTree 时，将 return 一个从根（也是列表）到每个叶子的路径列表，其中左边用 0 表示，右边用 0 表示1.

(define bTree-path
  (lambda (tree)
(cases bTree tree
  (leaf (datum) '())
  (node (value left right)
          (list (cons 0 (bTree-path left)) (cons 1 (bTree-path right)))))))

我的想法是，如果它看到一片叶子，那么它 return 与当前列表无关。但是，如果它是一个节点，则会创建一个新列表。在这个列表中，函数被递归地调用，用于左子树和右子树，cons 运算符分别为 0 和 1（意思是向左一步和向右一步）。这很快被证明是错误的，因为测试树的结果包含嵌套列表。结果应该类似于 ( (0 1) (0 0) (1) ) 这意味着有 3 片叶子可以通过左转两次、右转一次或左转然后右转找到。

从叶子到根的工作是行不通的，因为你不知道叶子是左叶还是右叶。每次找到节点时调用 list 都会导致嵌套。有没有一种方法可以使用左右子树的两个递归调用同时简单地调用两个列表？可能是函数或操作？

Answer 1

由于 (bTree-path left) 的结果是（或者至少应该是）从 left 到该子树中的叶子的所有路径的列表，因此您需要添加 0 这些路径中的每一个。
右子树也是如此。

对列表的每个元素做某事的函数是map:

(map (lambda (path) (cons 0 path)) (bTree-path left))

接下来，您想将两个路径列表（从左到右）合并到一个列表中，执行此操作的函数是 append。

把它们放在一起留作练习。

使用数据类型和递归在方案中制作列表列表

Making a list of lists in scheme using datatypes and recursion

recursion

scheme

list

racket