到目前为止,您???
需要评估叶子的价值,即。(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
. 我们可以嵌套if
s,但方案的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")]))
如果这是家庭作业,我会停在那里,并让您满意地理解和解决剩下的问题。我希望我的解释能给你更多的方向,只是“这里是代码”的答案。