recorrido pseudocodigo profundidad grafos genealogico ejemplos construccion busqueda binarios binario arboles arbol prolog logic-programming catalan instantiation-error

pseudocodigo - Enumerando árboles binarios en Prolog



profundidad de un arbol en prolog (2)

El uso de la biblioteca CLPFD ayudará a dar una solución limpia para generar los tamaños. Entonces no necesitas un integer/1 predicado wonky (;)), que puede ser problemático:

:- use_module(library(clpfd)). bintree(0,[]). bintree(1,[[],[]]). bintree(N, [L, R]) :- N #> 1, N #= N1 + N2 + 1, N1 #>= 0, N2 #>= 0, bintree(N1, L), bintree(N2, R).

O más simple (gracias a la sugerencia de @ repeat):

bintree(0,[]). bintree(N, [L, R]) :- N #> 0, N #= N1 + N2 + 1, N1 #>= 0, N2 #>= 0, bintree(N1, L), bintree(N2, R). ?- bintree(4, L). L = [[], [[], [[], [[], []]]]] ; L = [[], [[], [[[], []], []]]] ; L = [[], [[[], []], [[], []]]] ; L = [[], [[[], [[], []]], []]] ; L = [[], [[[[], []], []], []]] ; L = [[[], []], [[], [[], []]]] ; L = [[[], []], [[[], []], []]] ; L = [[[], [[], []]], [[], []]] ; L = [[[], [[], [[], []]]], []] ; L = [[[], [[[], []], []]], []] ; L = [[[[], []], []], [[], []]] ; L = [[[[], []], [[], []]], []] ; L = [[[[], [[], []]], []], []] ; L = [[[[[], []], []], []], []] ; false. ?-

CLPFD es una forma agradable y declarativa de expresar restricciones numéricas.

Estoy tratando de crear reglas Prolog para enumerar ''árboles binarios'' en forma de lista en Prolog. Soy nuevo en Prolog.

Un árbol con 0 nodos es una lista vacía:

[]

Un árbol con 1 nodo es:

[[],[]]

Un árbol con 2 nodos tiene 2 posibilidades:

[[],[[],[]]] [[[],[]],[]]

y así.

Aquí están mis reglas:

bintree(0,[]). bintree(1,[[],[]]). bintree(N,[Lc,Rc]) :- N > 1, bintree(N1,Lc), bintree(N2,Rc), N1 >= 0, N2 >= 0, N3 is N1+N2+1, N==N3.

Las consultas para 0 y 1 obviamente funcionan. Para N = 2, imprime una de las posibilidades, pero da un error después de ingresar el punto y coma para obtener la otra posibilidad. Las consultas para N> 2 dan un error directamente. El error es siempre el mismo:

ERROR: >/2: Arguments are not sufficiently instantiated

Leí sobre este error en algunos sitios web, pero no puedo entender qué está causando este error aquí.

Gracias por su ayuda con anticipación.


Sé que publiqué esta pregunta hace un año, pero logré resolverla más tarde sin utilizar ninguna biblioteca. Aquí está mi solución:

%binary tree generator bintree(0,[]). %0 nodes - empty list bintree(1,[[],[]]). %1 node - list containing 2 empty lists bintree(N,[Cl,Cr]) :- N>=2, %check only if at least 2 nodes between(0,N,Nl), %let Nl be in [0,N] between(0,N,Nr), %similarly for Nr Ns is Nl+Nr+1, %total no. of nodes should add up correctly N==Ns, %so check for that bintree(Nl,Cl), %children should also be valid binary trees bintree(Nr,Cr).