Обход дерева в обратном порядке на Прологе

Обход дерева относится к процессу систематического посещения каждого узла в древовидной структуре данных. Обход postorder на следующем изображении

Sorted_binary_tree

возвращает A, C, E, D, B, H, I, G, F (left, right, root). Код Пролога для обхода PREORDER:

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

preorder(void,[]).

Я хотел бы изменить приведенный выше код для реализации обратного обхода.


prolog dcg
person Mark    schedule 08.05.2012    source источник

Ответы (2)


arrow_upward
0
arrow_downward

В случае обратного заказа вам нужно пройти по левой ветви и получить список значений узла Left, затем пройти по правой ветви и получить список значений узла Right и, наконец, вернуть конкатенацию левого, правого и node value.

Следовательно, для изменения вашего кода нужно изменить способ создания результирующего списка:

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

Однако обратите внимание, что этот код неоптимален в том смысле, что он не является хвостовой рекурсией. Вы должны рассмотреть возможность реализации этого с помощью аккумулятора.

person gusbro    schedule 08.05.2012

arrow_upward
5
arrow_downward

Ребята, рассмотрите возможность использования DCG при описании списков, например:

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

Использование:

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

Вы получаете разные заказы, просто решая, где разместить [X] в последовательности.

person mat    schedule 08.05.2012