이진 가계도의 자손을 찾으려면

Question

이것은 이진 가계도의 자손을 찾는 체계 프로그램입니다 (사람의 아버지와 두 명의 아들 - bst가 있습니다). 사람의 이름과 나무 입력으로 주어집니다. 나는 여기서 주요 문제가 getsons 함수라고 생각한다. 이 기능을 어떻게 바꿔야합니까?

(define (getfather FAMT)` 
    (car FAMT) 
    ) 


(define (getson1 FAMT) 
    (cadr FAMT) 
) 

(define (getson2 FAMT) 
    (caddr FAMT) 
) 

(define (getsons FAMT) 
(cdr FAMT) 
) 

(define (empty? FAMT) 
(null? FAMT) 
) 

(define (nosons? FAMT) 
(and (empty? (getson1 FAMT)) (empty? (getson2 FAMT))) 
) 

(define (getd FAMT) 
(cond ((empty? FAMT) '()) 
     ((nosons? FAMT) '()) 
     ((empty? (getson1 FAMT)) (getson2 FAMT)) 
     ((empty? (getson2 FAMT)) (getson1 FAMT)) 
     (else (getd (getsons FAMT)))) 
) 

(define (main1 person FAMT) 
(cond ((empty? FAMT) (getd '())) 
     ((equal? person (getfather FAMT)) (getd FAMT)) 
     (else (main1 person (getsons FAMT)))) 
) 



(define FAMT '(Pierce (Mark (Peter()()) (Blaise()())) (James()()))) 

</code> 

Answer 1

Both getd 및 main1이 잘못되었습니다. getd에서 아들 중 하나가 누락 된 경우 재귀 적으로 다른 아들에 getd을 호출해야하며 else 케이스는 에 모두 아들을 반복적으로 호출하고 대답을 결합해야합니다. 어쨌든 솔루션은 너무 복잡합니다. 두 가지 경우 만 필요합니다. 트리가 비어 있거나 비어 있지 않습니다. 전체 트릭은 두 하위 트리의 답변을 결합하는 방법을 아는 데 있습니다. 요소를 추가하여 출력 목록 :

; returns a list of all descendants, including node at the root 
(define (getd FAMT) 
    (cond ((empty? FAMT) 
     '()) 
     (else 
     (append (list (getfather FAMT)) 
       (getd (getson1 FAMT)) 
       (getd (getson2 FAMT)))))) 

마찬가지로, main1는 사람이 발견되면 두 아들의 결과를 결합해야하며, 우리가 모르는 있기 때문에, 나무의 양쪽에 찾고 반복적으로 유지하고 그 답을 결합해야 어느 쪽이 검색된 사람입니까? (나무가 분류되지 않는 것 같습니다) :

; finds a person and returns a list with all of 
; its descendants, the list excludes the person 
(define (main1 person FAMT) 
    (cond ((empty? FAMT) 
     '()) 
     ((eq? person (getfather FAMT)) 
     (append (getd (getson1 FAMT)) 
       (getd (getson2 FAMT)))) 
     (else 
     (append (main1 person (getson1 FAMT)) 
       (main1 person (getson2 FAMT)))))) 

마지막으로, 전자 큰 나무는 테스트를 위해, 질문의 샘플 나무는 예를 들어, 가능한 모든 경우에 적용되지 않습니다

(define FAMT 
    '(Pierce 
    (Mark 
    (Peter 
     (Logan()()) 
    ()) 
    (Blaise 
    () 
     (Kurt()()))) 
    (James 
    () 
    ()))) 

(main1 'Mark FAMT) 
=> '(Peter Logan Blaise Kurt)