Путь схемы в двоичном дереве

Question

У меня есть упражнение, чтобы найти путь двоичного дерева в Схеме. В принципе, это похоже на поиск всех путей от корня до листьев дерева в схеме. Но вместо того, чтобы печатать значение узлов, мы должны напечатать способ добраться до листа. (печать: правая левая левая правая для ex)

Answer 1

Если вы говорите о поиске пути от корня до определенного листа, вы можете в основном искать свое дерево рекурсивно, и при этом вы должны передать список своей функции поиска в качестве параметра для отслеживания уже пройденного пути, и функция поиска должна возвращать список путей.

Например, предположим, что вы ищете L в своем дереве, вам нужно проверить, находится ли L в левом или правом поддереве. После нахождения поддерева, в котором L расположен вы можете в основном добавить направление в список пути, вы можете сделать что-то вроде

(define (search L tree) 
    (cond 
      ((null? tree) '() ) 
      ((member L leftsubtree) (cons 'left (search L leftsubtree)) 
      ((member L rightsubtree) (cons 'right (search L rightsubtree))))) 

Что мы делаем здесь мы нашли поддерево L расположен, а затем добавить направление (слева или справа) до начала пути от родителя этого поддерева до L. Конечно, если вы скопируете и вставьте этот код, это не сработает. Поэтому вам нужно реализовать эту функцию в соответствии с вашим древовидным представлением, и вам, вероятно, потребуется реализовать функцию-член для вашего случая. Я надеюсь, что это помогает.

Answer 2

(define (ab-chemin-aux AB e CH) 
(if (ab-noeud? AB) 
(if (equal? e (ab-etiquette AB)) 
CH 
(or (ab-chemin-aux (ab-gauche AB) e (append CH (list "gauche"))) 
(ab-chemin-aux (ab-droit AB) e (append CH (list "droit")))))#f)) 
(define (ab-chemin AB e) 
(ab-chemin-aux AB e (list))) 

Я понял ответ, но я забыл про вас здесь. Спасибо за ваш ответ. Надеюсь, что это поможет кому-то