Árbol postorder transversal en Prolog

dcg

Question

Recorrido de árbol se refiere al proceso de visitar cada nodo en una estructura de datos de árbol de una manera sistemática. El recorrido del postorder en la siguiente imagen

Sorted_binary_tree

devuelve A, C, E, D, B, H, I, G, F (left, right, root) . El código de Prolog para el PREORDER es

preorder(tree(X,L,R),Xs) :-
    preorder(L,Ls),
    preorder(R,Rs),
    append([X|Ls],Rs,Xs).

preorder(void,[]).

Me gustaría modificar el código anterior para implementar el recorrido del posttorder.

Answer 1

En el caso de un postorder, debe atravesar la rama izquierda y obtener una lista de valores de nodo Left , luego recorrer la rama derecha y obtener una lista de valores de nodo Right , y finalmente devolver la concatenación de Left, Right y el node value .

Por lo tanto, modificar su código sería reorganizar la forma en que crea una instancia de la lista resultante:

postorder(tree(X, L, R), Xs):-
  postorder(L, Ls),
  postorder(R, Rs),
  append(Ls, Rs, Xs1),
  append(Xs1, [X], Xs).
postorder(void, []).

Sin embargo, tenga en cuenta que este código es subóptimo en el sentido de que no es recursivo de cola. Debería considerar implementarlo con la ayuda de un acumulador.

Answer 2

Gente, considere usar DCG al describir listas, por ejemplo:

preorder(void) --> [].
preorder(tree(X, L, R)) -->
        [X],
        preorder(L),
        preorder(R).

Uso:

?- phrase(preorder(Tree), List).

Obtendrá diferentes órdenes simplemente decidiendo dónde colocar la [X] en la secuencia.