> 1 <

Автор Сообщение

Rex

Members


Статус

2 сообщений

Где: Russia
Род занятий:
Возраст:

#442   2009-06-28 19:04 GMT+3 часа(ов)      
Не мог бы кто-нибудь мне помочь? Уже несколько дней сижу, но ничего не получается. Задача такая:

Дано бинарное дерево. Две вершины помечены. Вывести все пути, которые проходят хотя бы через одну помеченную вершину.

Заранее спасибо...

Yakov

Members


Статус

4 сообщений
http://solveforfun.blogspot.com
Где: Russia
Род занятий: Yakov
Возраст:

#443   2009-06-29 15:36 GMT+3 часа(ов)      
Вот что у меня получилось. Надеюсь поможет. Тут правда никак не учитывается, что две вершины помечены.
 
#lang scheme
;Дано бинарное дерево. Две вершины помечены.
;Вывести все пути, проходящие через эти вершины.
 
;Путь по дереву обозначается последовательностью нулей и единиц, где 0 обозначает
;cпуск по левому поддереву, а 1 по правому.
 
;Вершина дерева состоит из метки, левой и правой ветки или из одной метки.
 
(define (make-path mark)
(list '() mark))
 
(define (add-step path step mark)
(list (cons step (car path)) (or (marked? path) mark)))
 
(define (marked? path)
(cadr path))
 
(define (mark path m)
(list (car path) m))
 
(define (leave? tree)
(not (pair? tree)))
 
(define (left-branch tree)
(cadr tree))
 
(define (right-branch tree)
(caddr tree))
 
(define (value tree)
(car tree))
 
(define (paths tree)
(cond ((leave? tree) (list (make-path tree)))
(else (append (map (lambda (path) (add-step path 0 (value tree)))
(paths (left-branch tree)))
(map (lambda (path) (add-step path 1 (value tree)))
(paths (right-branch tree)))))))
 
(filter marked? (paths '(#f (#t #f #t) (#f #f #f))))
 
;(marked? (mark (add-step (add-step (make-path #t) 0) 1) #f))
 

Rex

Members


Статус

2 сообщений

Где: Russia
Род занятий:
Возраст:

#450   2009-06-30 19:14 GMT+3 часа(ов)      
Большое спасибо! Вы мне очень помогли.
> 1 <


Онлайн :

0 пользователь(ей), 30 гость(ей) :




Реклама на сайте: