Поиск количества совпадающих элементов в бинарном дереве

@STRANN1K_454 · Регистрация: 19.09.2015

Author24 — интернет-сервис помощи студентам

Здравствуйте. Нужно найти количество совпадающих элементов в бинарном дереве. Я написал следующие правила

Prolog

element(t(X,_,_), X).
element(t(_, Left, Right), X) :- element(Left,X);element(Right,X).
 
counter(nil,_,0) :- !.
counter(t(K,TL,TR),K,N) :- counter(TL,K,NL), counter(TR,K,NR), N is NL+NR+1.
counter(t(_,TL,TR),K,N) :- counter(TL,K,NL), counter(TR,K,NR), N is NL+NR.
 
func(Tree) :- element(Tree, Elements), func(Tree), counter(Tree, Elements, Num),
write(Elements), write('-'), write(Num), nl.

но получается не то что хотел.

Например:

Prolog

?- func(t(158,t(158,nil,nil), t(152,nil,nil))).
158-2
 
yes

а расчитывал на

Prolog

?- func(t(158,t(158,nil,nil), t(152,nil,nil))).
158-2
158-2
152-1
 
yes

По отдельности element и counter работают, соответственно 1-й выводит все элементы дерева, а 2-й кол-во вхождений элемента в дерево. Помогите разобраться в чем же дело

@Black Fregat · 23.11.2015, 05:49

Сообщение от STRANN1K_454

расчитывал на

Не совсем понятно, почему Вы на это рассчитывали.
Приведенный вариант вообще входит в бесконечную рекурсию на вложенном вызове func

Нужно написать что-то вроде

Prolog

func(Tree) :- 
    element(Tree, Elements),    % <--- Здесь возникает развилка
    counter(Tree, Elements, Num),
    write(Elements), write('-'), write(Num), nl,
    fail;    % <--- Здесь происходит принудительный откат к развилке
    write('---').   % <--- А сюда попадём, когда варианты перебора в развилке закончатся

И обязательно поставьте дополнительное отсечение во втором правиле counter, иначе получите много неправильных вариантов.

@STRANN1K_454 · 23.11.2015, 06:49 **[ТС]**

Сообщение от Black Fregat

Не совсем понятно, почему Вы на это рассчитывали.
Приведенный вариант вообще входит в бесконечную рекурсию на вложенном вызове func

Да, func там и вправду не нужен. Я его добавил в попытках отладки, а затем случайно скопировал в сообщение. Заметил это по истечении 5 минут и не смог отредактировать.

Все заработало, спасибо огромное!

@STRANN1K_454 0 / 0 / 0 Регистрация: 19.09.2015 Сообщений: 2
	23.11.2015, 06:49 [ТС]	3
	Сообщение от Black Fregat Не совсем понятно, почему Вы на это рассчитывали. Приведенный вариант вообще входит в бесконечную рекурсию на вложенном вызове func Да, func там и вправду не нужен. Я его добавил в попытках отладки, а затем случайно скопировал в сообщение. Заметил это по истечении 5 минут и не смог отредактировать. Все заработало, спасибо огромное! 0

Опции темы

Поиск количества совпадающих элементов в бинарном дереве

Решение