Бинарные деревья в Прологе - PullRequest
Новая
       25

Бинарные деревья в Прологе

0 голосов
/ 21 апреля 2011

Мне нужно написать прологическую программу, которая считывает с клавиатуры такие положительные числа, пока пользователь не напишет «стоп» и не создаст двоичный словарь без дубликатов.

Я пытаюсь: 

:-dynamic tree/1.

 run:-
     retractall(tree(_)),
     write('Input N '), read(N),
     insert(N,empty,T),
     assert(tree(T)),
     start(N),nl,
     tree(T),write(T),!.

start(stop):-!.
start(N):-
      N \= stop,
      tree(T),
      insert(N,T,NewTree),
      assert(tree(NewTree)),
      write('Input N '), read(M),
      start(M).

insert(NewItem,empty,tree(NewItem,empty,empty)):- !.
insert(NewItem,tree(Element,Left,Right),tree(Element,NewLeft,Right)):-
                                                                  NewItem @< Element,
                                                                  !,insert(NewItem,Left,NewLeft).

insert(NewItem,tree(Element,Left,Right),tree(Element,Left,NewRight)):-
                                                                  insert(NewItem,Right,NewRight).

Можеткто-нибудь мне помочь?

1 Ответ

1 голос
/ 29 марта 2012

Две ошибки здесь. Прежде всего, первый элемент вставляется дважды из-за явного вызова insert в теле run, а также из-за вызова start, который также вызовет insert. Вместо этого вам нужно начать с записи пустого дерева. Во-вторых, недостаточно узнать, какое дерево записывается в данный момент, вам нужно удалить предыдущую версию дерева и записать текущую.

Исправление этих двух ошибок приводит к следующему решению: 

:-dynamic tree/1.

 run:-
     retractall(tree(_)),
     write('Input N '), read(N),
     assert(tree(empty)),  % 1. initially the tree is empty
     start(N),nl,
     tree(T),write(T),!.

start(stop):-!.
start(N):-
      N \= stop,
      retract(tree(T)), % 2. changed here
      insert(N,T,NewTree),
      assert(tree(NewTree)),
      write('Input N '), read(M),
      start(M).

insert(NewItem,empty,tree(NewItem,empty,empty)):- !.
insert(NewItem,tree(Element,Left,Right),tree(Element,NewLeft,Right)):-
       NewItem @< Element,
       !,insert(NewItem,Left,NewLeft).

insert(NewItem,tree(Element,Left,Right),tree(Element,Left,NewRight)):-
        insert(NewItem,Right,NewRight).

В немного другой заметке вы можете спросить себя, действительно ли вам нужно делать все это утверждение / убирание, поскольку вы можете передать построенное в данный момент дерево как аргумент начального предиката.

Устранение утверждений и отказов дает следующую версию: 

run:-
     write('Input N '), read(N),
     start(N, empty, T),nl,
     write(T).

start(stop, T, T):-!.
start(N, CurTree, FinalTree):-
      N \= stop,
      insert(N,CurTree,NewTree),
      write('Input N '), read(M),
      start(M, NewTree, FinalTree).

insert(NewItem,empty,tree(NewItem,empty,empty)):- !.
insert(NewItem,tree(Element,Left,Right),tree(Element,NewLeft,Right)):-
       NewItem @< Element,
       !,insert(NewItem,Left,NewLeft).

insert(NewItem,tree(Element,Left,Right),tree(Element,Left,NewRight)):-
        insert(NewItem,Right,NewRight).

Наконец, обратите внимание, что вырезание в первом предложении start и предполагаемое использование stop с привязкой первого и второго аргументов при свободном третьем аргументе делает явную проверку N \ = stop избыточной. Это дает нам окончательный вариант решения: 

run:-
     write('Input N '), read(N),
     start(N, empty, T),nl,
     write(T).

start(stop, T, T):-!.
start(N, CurTree, FinalTree):-
      insert(N,CurTree,NewTree),
      write('Input N '), read(M),
      start(M, NewTree, FinalTree).

insert(NewItem,empty,tree(NewItem,empty,empty)):- !.
insert(NewItem,tree(Element,Left,Right),tree(Element,NewLeft,Right)):-
       NewItem @< Element,
       !,insert(NewItem,Left,NewLeft).
insert(NewItem,tree(Element,Left,Right),tree(Element,Left,NewRight)):-
        insert(NewItem,Right,NewRight).
...