1

我已经将辅助函数定义为：

;; returns value of node
(define (value node)
  (if (null? node) '()
      (car node)))

;; returns left subtree of node
(define (left node)
  (if (null? node) '()
      (cadr node)))

;; returns right subtree of node
(define (right node)
  (if (null? node) '()
      (caddr node)))

我正在尝试编写一个函数leaves，该函数按从左到右的顺序返回一个带有树叶的列表。

(define (leaves tree)
    (if (and (?null (left tree)) (?null (right tree)))
        ???
        (leaves (left tree)) (leaves (right tree))))

但这是我所能得到的

例如： (leaves '(1 (2 () ()) (3 () ()))) 应该评估为 '(2 3)

4

3 回答 3

1

到目前为止，您???需要评估叶子的价值，即。(value node)因为它是您迭代的基本情况。此外，您将需要在迭代案例中组合从基本案例返回的值。 list当您需要组合多个结果时，通常是第一个尝试的好选择，cons通常是我的第二次尝试。接受这些建议，您的leaves函数如下所示：

(define (leaves tree)
    (if (and (null? (left tree)) (null? (right tree)))
        (value tree)
        (list (leaves (left tree)) (leaves (right tree)))))

其中，当在您的样本上运行时，(leaves '(1 (2 () ()) (3 () ())))确实评估为(2 3).

然而; 你还没有完成！我们仅使用 1 级递归进行测试。如果我们做一棵更大的树呢？类似的东西：(leaves '(1 (2 (4 () ()) (5 () ())) (3 (6 () ()) (7 () ())))) 运行这个给出((4 5) (6 7)). 这些是按正确顺序排列的正确值，但我们有太多的结构，太多的括号。这是您在整个计划生涯中都会遇到的典型问题，所以让我解释一下为什么会发生这种情况，以及如何着手解决这个问题。

如果查看我们if表单的两个分支，您会注意到它(value tree)返回一个原子，或者在这种情况下返回一个数字。else 分支取两个 of???并将其转换为???. 我们将多次执行 else 分支——只要我们不在基本情况下。这意味着我们将继续包裹，包裹，包裹到越来越深的列表结构中。所以这就是我们要做的。

让我们在基本情况下返回一个列表，并在递归情况下保持我们的列表平坦。要在我们的基本情况下返回一个列表，它就像 return(list (value tree))而不是 just一样简单(value tree)。在递归的情况下，我们需要一个函数，它需要 2 个列表并将它们组合起来，而不需要创建更深的列表。这样的功能确实存在 - append。那么让我们看看我们的leaves函数现在是什么样子的：

(define (leaves tree)
        (if (and (null? (left tree)) (null? (right tree)))
            (list (value tree))
            (append (leaves (left tree)) (leaves (right tree)))))

间奏曲 - 测试用例

Racket 有一个测试套件库，它的进入门槛非常低，称为rackunit。让我们在文件底部汇总几个快速测试用例。

(require rackunit)
;;empty tree
(check-equal? (leaves '()) '())

;;simple balanced tree
(check-equal?
 (leaves '(1 (2 () ()) (3 () ())))
 '(2 3))

;;larger balanced tree
(check-equal?
 (leaves '(1 (2 (4 () ()) (5 () ())) (3 (6 () ()) (7 () ()))))
 '(4 5 6 7))

;;unbalanced tree
(check-equal?
 (leaves '(1 (2 (4 () ()) ()) (3 () ())))
 '(4 3))

最近，racket 增加了对子模块的支持和对测试子模块的特定支持，如果您好奇并想研究它们。

回到我们的叶子问题。运行我们的测试，我们注意到我们的函数在不平衡的树上表现不佳。()当我们有一个只有 1 个叶子的节点时，我们会得到额外的 s。那是因为每当我们在一个不是叶子的节点处时，我们都会遍历左子树和右子树。我们真正需要的是我们的if. 我们可以嵌套ifs，但方案的cond形式更有意义。

现在，我们要填写的模板是：

(define (leaves tree)
  (cond [(leaf? tree) (...)]
    [(and (has-left? tree) (has-right? tree)) 
     (...)]
    [(has-left? tree) (...)]
    [(has-right? tree) (...)]
    [else (error "should never get here")]))

如果这是家庭作业，我会停在那里，并让您满意地理解和解决剩下的问题。我希望我的解释能给你更多的方向，只是“这里是代码”的答案。

于 2012-10-08T15:26:52.793 回答
1

好吧，这似乎您正在执行广度优先搜索，但是如果您有两个孩子（或者只有一个，如果您不想打印只有一个孩子的节点），您不会打印自己。

我的目标是首先解决这个问题，然后改变你的解决方案来解决这个问题。

于 2012-10-05T19:23:22.137 回答
0 
(define (list-of-leaves tree)
  (if(leaf? tree)
     (list (node tree))
     (cond((right-branch-only? tree)(list-of-leaves (right-branch tree)))
          ((left-branch-only? tree)(list-of-leaves (left-branch tree)))
          (else(append (list-of-leaves (left-branch tree))
                       (list-of-leaves (right-branch tree)))))))
于 2013-10-26T19:10:23.423 回答