Arbres binaires dans Prolog

Question

J'ai besoin d'écrire un programme prologue qui lit depuis le clavier de tels nombres positifs jusqu'à ce que l'utilisateur écrit 'stop' et construit un dictionnaire binaire sans doublons.

J'essaie:

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

Quelqu'un peut-il me aider?

Answer 1

Deux erreurs ici. Tout d'abord, le premier élément est inséré deux fois en raison de l'appel explicite à insérer dans le corps de run, et à l'appel de démarrer qui appellera également insert. Au lieu de faire cela, vous devez commencer par enregistrer l'arbre vide. Deuxièmement, il ne suffit pas de consulter l'arbre en cours d'enregistrement, vous devez supprimer la version précédente de l'arbre et enregistrer la version actuelle.

La résolution de ces deux erreurs conduit à la solution suivante:

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

Sur une note légèrement différente, vous pourriez vous demander si vous avez vraiment besoin de faire tout ce assertive/rétractant que vous pouvez passer l'arbre actuellement construit en tant qu'argument du prédicat de départ.

L'élimination affirme et escamote donne la version suivante:

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

Enfin, constater que la coupe dans la première clause de départ et l'utilisation prévue de la butée avec la première et la deuxième arguments étant lié alors que le troisième l'un étant libre, rend le contrôle explicite N \ = stop redondant. Cela nous donne la version finale de la 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).