Повторяющиеся элементы бинарного дерева - Prolog

Узнай цену своей работы

Формулировка задачи:

Необходимо на Turbo Prolog 2.0 вывести все повторяющиеся элементы бинарного дерева. Была похожая тема, но программа не работала.

Решение задачи: «Повторяющиеся элементы бинарного дерева»

textual
Листинг программы
domains 
int=integer
intl=int*
btree=tree(int,btree,btree); nil 
       
predicates
 
task(btree,intl)
b2l(btree,intl)
app(intl,intl,intl)
del(int,intl,intl)
memb(int,intl)
dups(intl,intl)
 
clauses
 
b2l(nil,[]).
b2l(tree(V,L,R),X) :- b2l(L,LL), b2l(R,RR), app(LL,[V],L1), app(L1,RR,X).
 
app([],X,X).
app([H|T],X,[H|R]) :- app(T,X,R).
 
del(_,[],[]).
del(H,[H|T],R):- del(H,T,R).
del(H,[Z|T],[Z|R]):- Z<>H, del(H,T,R).
 
memb(_,[]) :- fail.
memb(X,[X|_]):- !.
memb(X,[Y|T]):- X<>Y, memb(X,T).
 
dups([],[]).
dups([H|T],[H|R]) :- del(H,T,TT), memb(H,T), dups(TT,R).
dups([H|T],R) :- del(H,T,TT), not(memb(H,T)), dups(TT,R).
 
task(B,R) :- b2l(B,BB), dups(BB,R).

Объяснение кода листинга программы

В представленном коде на языке Prolog описывается работа с бинарными деревьями и повторяющимися элементами.

  1. Объявления:
    • domains: определения типов данных, используемых в программе. В данном случае, int - это целочисленный тип данных, intl - это массив (вектор) целочисленных значений. Также определено типовое представление бинарного дерева - btree.
    • predicates: здесь перечислены все предикаты (отношения), которые используются в программе.
    • clauses: это правила, определяющие поведение предикатов.
  2. Первое правило b2l(nil,[]) говорит, что если в качестве аргументов функции b2l выступает корень (nil), то результатом будет пустой список [].
  3. Второе правило b2l(tree(V,L,R),X) говорит, что если в качестве аргументов функции b2l выступает не корень (то есть у дерева есть левое и правое поддеревья, а также значение V), то результатом будет список X, полученный путем объединения результатов обхода левого и правого поддеревьев с добавлением значения V.
  4. Следующие два правила app([],X,X) и app([H|T],X,[H|R]) определяют поведение функции app, которая добавляет элемент X в список, предварительно разделенный на голову (H) и хвост (T).
  5. Правила del(_,[],[]), del(H,[H|T],R) и del(H,[Z|T],[Z|R]) определяют поведение функции del, которая удаляет элемент с заданным ключом из списка.
  6. Правила memb(,[]) и memb(X,[X|]) определяют поведение функции memb, которая проверяет, является ли элемент X частью списка.
  7. Правила dups([],[]) и dups([H|T],[H|R]) определяют поведение функции dups, которая находит все повторяющиеся элементы в списке.
  8. Последнее правило task(B,R) :- b2l(B,BB), dups(BB,R) говорит, что функция task преобразует бинарное дерево B в список BB, а затем с помощью функции dups находит все повторяющиеся элементы в этом списке и возвращает их в виде результата R.

Оцени полезность:

6   голосов , оценка 4.333 из 5
Похожие ответы