0

我正在制作一个函数来检查一个项目是否是树中叶子的成员。

这就是我到目前为止所拥有的。但它工作不正常。一些应该为真的输入返回假。请帮忙？

(define (leaf-member? item tr)
 (cond
  [(empty-tree? tr) #f]
  [(leaf? tr)
      (if (equal? item tr) #t
          #f)]
  [else (leaf-member? item (cdr tr))]))

这是它应该返回的内容：

~(leaf-member? 'a (leaf 'a))
#t
4

3 回答 3

0

在树中查找项目的代码取决于树的定义。特别是，如果您定义一棵由子树组成的树，那么这表明您将如何在树上递归。因此，您需要从“树”和“叶”的定义开始。

这是一个完整的解决方案，没有假设二叉树。

(define (make-tree item children)
  `(TREE ,item ,children))
(define (tree? thing)
  (and (list? thing)
       (= 3 (length thing))
       (eq? 'TREE (car thing))))
(define tree-item cadr)
(define tree-children caddr)

(define (make-leaf item)
  (make-tree item '()))
(define (leaf? tree) 
  (and (tree? tree) (null? (tree-children tree)))

(define (leaf-member? tester item tree)
  (and (tree? tree)
       (or (and (leaf? tree) (tester item (tree-item tree)))
           (let looking ((subtrees (tree-children tree)))
              (and (not (null? subtree))
                   (or (leaf-member? equal item (car subtrees))
                       (looking (cdr subtrees)))))))
于 2013-03-26T03:13:27.173 回答
0

看来您不是在使用树，而是在使用列表。我这么说是因为如果你在一棵树中，那么你搜索的不是列表的其余部分（'cdr'），而是左右分支。

如果您发布如何创建非叶树以更好地建议您，这将有所帮助，但无论如何您的最终陈述不应该是这样的：

[else (leaf-member? item (cdr tr))]

但像这样：

[else (or (leaf-member? item (left-branch tr))
          (leaf-member? item (right-branch tr)))]
于 2013-03-26T01:29:25.023 回答
0

你已经接近答案了。要修复它，您必须：

  1. 将提供的值与叶子中item的实际值进行比较（而不是叶子本身！）
  2. 正确推进两个子树的递归。请注意，cdr在这里使用没有任何意义，这是我们正在遍历的树，而不是列表。

在这两种情况下，请使用适当的访问器过程。我会尝试猜测它们的名字，将它们调整为您自己的实现：

(define (leaf-member? item tr)
  (cond
    [(empty-tree? tr)
     #f]
    [(leaf? tr)
     (if (equal? item (tree-value tr))
         #t
         #f)]
    [else
     (or (leaf-member? item (tree-left tr))
         (leaf-member? item (tree-right tr)))]))
于 2013-03-26T01:34:09.920 回答