Найти потомков человека бинарного генеалогического дерева (схема lang)

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

И то и другое getd а также main1 неверны. В getd, случаи, когда один из сыновей пропал без вести, должны рекурсивно вызывать getd на другом сыне, а else дело должно рекурсивно вызывать getd на обоих сыновей и совмещаем ответ. И в любом случае, решение слишком сложное, на самом деле требуются только два случая: либо дерево пустое, либо непустое, весь трюк заключается в том, чтобы знать, как объединить ответы из обоих поддеревьев, я решил добавить элементы для создания список вывода:

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