Binary trees in Prolog

I need write a prolog program that read from keyboard such positive numbers until the user writes 'stop' and builds a binary dictionary without duplicates.

I try:

:-dynamic tree/1.

 run:-
     retractall(tree(_)),
     write('Input N '), read(N),
     insert(N,empty,T),
     assert(tree(T)),
     start(N),nl,
     tree(T),write(开发者_C百科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).

Can anyone help me?

---

Two mistakes here. First of all, the first element is being inserted twice due to the explicit call to insert in the body of run, and to the call to start that will also call insert. Instead of doing this, you need to start by recording the empty tree. Second, it is not enough to consult which tree is currently being recorded, you need to remove the previous version of the tree and record the current one.

Fixing these two mistakes leads to the following solution:

:-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).

On a slightly different note, you might ask yourself whether you really need to do all this asserting/retracting as you can pass the currently constructed tree as an argument of the start predicate.

Eliminating asserts and retracts gives the following version:

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).

Finally, observe that the cut in the first clause of start and the intended use of stop with the first and the second arguments being bound while the third one being free, makes the explicit check N\= stop redundant. This gives us the final version of the solution:

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).