Решение упражнения 2.28 из SICP
Процедура fringe будет производить обход дерева в глубину слева направо и собирать узлы в порядке обхода в один список. Ее структура очень похожа на структуру count-leaves. При рассмотрении каждого узла также рассматриваются три случая: пустое дерево, листовой элемент и нелистовой элемент (поддерево).
- Для пустого дерева на входе мы генерируем пустой список на выходе.
- Для листового элемента на входе генерируем список из этого одного элемента.
- Для нелистового элемента возвращаем список, составленный из списка для его первого поддерева, к которому добавлен с помощью append результат для этого же элемента без первого поддерева.
Получаем такую процедуру:
(define (fringe tree) (cond ((null? tree) ()) ((pair? tree) (append (fringe (car tree)) (fringe (cdr tree)))) (else (list tree))))
Она генерирует необходимый результат.
Comments
Comment from meduza
Date: October 25, 2008, 6:50 pm
Блин, так просто, а я намудрил…
(define (fringe lst)
(define (f lst acc)
(cond ((null? lst) acc)
((not (list? lst)) (cons lst acc))
(else (append (f (car lst) acc) (f (cdr lst) acc)))))
(f lst (list)))
но работает 
Comment from qMax
Date: January 16, 2009, 6:25 am
итеративная версия:
(define (fringe tree)
(define (fringe-elem elem)
(cond ((null? elem) ‘())
((pair? elem) (fringe elem))
(else (list elem))))
(define (iter src res)
(if (null? src)
res
(iter (cdr src)
(append res (fringe-elem (car src))))))
(iter tree ‘()))
Comment from qMax
Date: January 16, 2009, 6:26 am
пардон…
(define (fringe tree)
(define (fringe-elem elem)
(cond ((null? elem) '())
((pair? elem) (fringe elem))
(else (list elem))))
(define (iter src res)
(if (null? src)
res
(iter (cdr src)
(append res (fringe-elem (car src))))))
(iter tree '()))
Comment from JessicaFletcher
Date: March 18, 2009, 10:15 am
(define (fring list)
(cond (= (list null) null)
((notlist? list) list)
(else (cons (fring (car list) fring (cdr list)))))
Write a comment