(Scheme) 항목이 트리의 리프 멤버인지 확인합니다.

Question

항목이 트리의 리프 멤버인지 확인하는 함수를 만들고 있습니다.

이것은 내가 지금까지 가지고있는 것입니다. 그래도 제대로 작동하지 않습니다. 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 

Answer 1

답변에 가깝습니다.

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)))])) 

Answer 2

당신이 나무 만 목록으로 작동하지 않습니다. 나는 당신이 나무에 있다면 나머지 목록 ('cdr')이 아니라 왼쪽과 오른쪽 가지를 검색하기 때문에 그렇게 말합니다.

당신이 더 나은 조언을 비 잎 트리를 생성하는 방법을 게시 할 경우 도움이 될,하지만 어쨌든 최종 문이 안 :

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

을하지만,이 같은 :

[else (or (leaf-member? item (left-branch tr)) 
      (leaf-member? item (right-branch tr)))] 

Answer 3

트리에서 항목을 찾는 코드는 트리의 정의에 달려있다. 특히 하위 트리로 구성된 트리를 정의하면 트리에서 반복되는 방법을 나타냅니다. 따라서 '나무'와 '잎'의 정의부터 시작해야합니다.

여기에는 이진 트리를 전제로 한 완전한 해결책이 있습니다.

(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)))))))