Функция сортировки деревьев в схеме

Question

Я борюсь с этой проблемой более 2 дней и все еще как-то не могу ее решить. Мне нужно написать функцию в SCHEME, которая берет список в дереве и отображает элементы в отсортированном порядке.

Путь определяет дерева «(6 (левый ...) (справа ...))

Моей функции выбрать дерево:

(define (tree-sort tree) 
(cond ((null? tree) '()) 
    ((> (car tree) (cadr tree)) 
    (tree-sort (cadr tree))) 
    (else 
    (tree-sort (caddr tree)))) 
) 

Так что я думаю, я должен также есть функция, которая сортирует самый полный список? Я действительно не понимаю, и это последний раз, когда мне придется иметь дело со схемой. Я никогда не использовал stackoverflow, поэтому, пожалуйста, извините меня, если формирование неправильное.

Прошу поблагодарить вас!

Answer 1

Теперь, когда вы уточнили, что дерево уже отсортировано, вы ищете обход дерева in-order, который возвращает отсортированный список элементов. Я предполагаю, что вас интересует список . как выход, из-за базового случая, указанного в вопросе. Попробуйте что-то вроде этого:

(define (tree-sort tree) 
    (if (empty-tree? tree) 
     '() 
     (append (tree-sort (left-subtree tree)) 
       (list (value tree)) 
       (tree-sort (right-subtree tree))))) 

Используйте соответствующие процедуры для тестирования, если дерево пусто и для доступа значения каждого узла, левые и правые поддерев. Вышеупомянутая процедура вернет отсортированный список с значениями деревьев.