Бинарное Дерево.сумма Ключей В Узлах.

  • Автор темы Tony7161
  • Дата начала
T

Tony7161

Гость
#1
Здравствуйте.Столкнулся с такой проблемой.Дано дерево и определение "путь".Под "путем" понимается сумма ключей в узлах от корня до узла без сыновей.Например
5
/ \
8 9
/ \ \
3 2 6
1 путь 5+8+3=16
2 путь 5+8+2=15
3 путь 5+9+6=20
требуется написать псевдокод для рекурсивного алгоритма.Функция получает дерево и некоторую сумму и возвращает true если в дереве есть путь равный этой сумме или false если такого пути нет.Буду очень благодарен за теоретическое обьяснение решения этой задачи.
 
R

rrrFer

Гость
#2
ну поиск в глубину используй :)

Код:
f(tree(E,empty,empty),RS,S):-
S = RS + E, !.
f(tree(E,L,_),RS,S):-
TS = RS + E,
f( L, TS, S ).
f(tree(E,_,R),RS,S):-
TS = RS + E,
f( R, TS, S ).
не проверял, на прологе как-то так.