0

アイテムがツリーの葉のメンバーであるかどうかを確認する関数を作成しています。

これは私がこれまでに持っているものです。しかし、それは正しく機能していません。trueであるはずの入力の一部がfalseを返しています。助けてください？

(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

あなたは木ではなくリストを扱っているようです。ツリーにいる場合は、リストの残りの部分（'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 に答える
0

ツリー内のアイテムを検索するコードは、ツリーの定義によって異なります。特に、サブツリーで構成されるツリーを定義する場合、それはツリーでどのように再帰するかを示します。そのため、「tree」と「leaf」の定義から始める必要があります。

これが完全な解決策であり、二分木を想定していません。

(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 に答える