Quel est l'algorithme de vérification si un arbre binaire est un arbre binaire complet? (En utilisant Prolog).Comment écrire un prédicat complet d'arbre binaire en utilisant Prolog
Par exemple:
?- complete(nil).
true.
?- complete(tree(1,nil,nil)).
true.
?- complete(tree(1,tree(2,nil,nil),nil)).
false.
?- complete(tree(1,tree(2,nil,nil),tree(3,nil,nil))).
true.
complete(T) :- complete(T, _).
complete(nil, 0).
complete(tree(_, L, R), N) :-
complete(L, N1),
complete(R, N1),
N is N1 + 1.
mise à jour:
Il fonctionne pour moi:
?- complete(nil).
true.
?- complete(tree(1,nil,nil)).
true.
?- complete(tree(1,tree(2,nil,nil),nil)).
false.
?- complete(tree(1,tree(2,nil,nil),tree(3,nil,nil))).
true.
Cela ne fonctionne pas. Cela retourne vrai pour tous les exemples que j'ai montrés ci-dessus. Si j'ai compris ce que vous avez essayé de faire est de vérifier que le sous-arbre et le sous-arbre de gauche ont la même hauteur qui ne définit pas un arbre binaire complet. – user550413
@ user550413: l'avez-vous déjà essayé? parce que cela fonctionne avec moi, au moins pour les échantillons dans votre message! – salva
Quel est l'algorithme en anglais, pour commencer? –
Eh bien, j'ai besoin que toutes les feuilles soient à la même distance de la racine. Donc, l'algorithme le plus simple passe par tous et vérifie si tous ont la même distance depuis la racine. – user550413
Peut-être une approche légèrement plus rapide: Trouvez la profondeur d'une feuille, puis recherchez un nœud feuille qui a moins de profondeur ou un nœud non-feuille qui a une profondeur égale. Si vous trouvez l'un de ceux-ci, l'arbre binaire n'est pas "complet". – hardmath