Языковая схема, листовые деревья

Question

;; Дерево с маркировкой листьев (Llt) является одним из следующих:

;; * пусто

;; * (cons l1 l2), где l1 является непустым Llt, а l2 является Llt

;; * (cons v l), где v является Int и l является Llt

Как найти конкретный список в дереве с меткой листа? Например, если у меня есть параметр n, и я хочу найти, какой список содержит n. Что мне делать?

Answer 1

Итак, у вас есть пустое дерево, которое равно '() или (cons x y) где x и y могут быть либо целыми, либо поддерево. В основном это просто структура списка с числами?

Поскольку это может быть домашнее задание, я просто дать вам несколько советов по пути:

(define (locate tree x) 
    (cond ;; if it's not a pair we didn't find it 
     ((not (pair? <??>)) #f) 
     ;; if the car or the cdr of tree is x, return tree 
     ((or (eqv? <??> <??>) (eqv? <??> <??>)) <??>) 
     ;; answer must be in either the car OR the cdr 
     (else (or (locate <??> x) (locate <??> x))))) 

eqv? будет #T, если два eq? так вы можете найти часть дерева слишком , Например.

(define tree '(1 (2 (3 (4) 5 6 7 8)))) 
(locate tree 4) ; ==> (4) 
(locate tree (locate tree 4)) ; ==> ((4) 5 6 7 8) 

Но он работает только для структуры, которая составляет eq?. Например, это не сработает, если вы не используете equal?:

(locate tree '(4)) ; ==> #f