пролог проходит по нестандартному дереву слева направо

Мне нужно реализовать предикат trav(Tree,List), который выполняет обход дерева слева направо;

Где: Дерево определяется узлом структуры (левый, правый), где левый и правый могут быть либо другим узлом, либо любым элементом данных Пролога. Список - это список значений конечных узлов в дереве.

Например:

?- trav(x,L).
L = [x].
?- trav(node(1,node(2,node(a,b))),L).
L = [1, 2, a, b] .

Что у меня есть на данный момент:

trav(tree,[ ]).
trav(node(Left,Rigth), L) :-
    trav(Left, L),
    trav(Right, L),
    append(Left,[Left|Right],L).

tree prolog tree-traversal
person Zast    schedule 07.06.2015    source источник
comment
У вас снова проблема с тем, каким вы хотите видеть дерево! Определите сначала предикат is_tree/1, который определяет, что такое дерево, по вашему мнению. Это очень редко, но, безусловно, возможно иметь узлы без элементов. Такие узлы обычно встречаются для деревьев выражений. Но иначе их не бывает.   -  person false    schedule 07.06.2015
comment
Не мое мнение, это то, с чем мне дали работать.   -  person Zast    schedule 07.06.2015

Ответы (1)


arrow_upward
2
arrow_downward

Мой Пролог немного заржавел, но я считаю, что это должно сработать:

node(Left, Right).

trav(node(Left, Right), L) :- 
  trav(Left, L1), 
  trav(Right, L2),
  append(L1, L2, L).
trav(X, [X]) :- X \= node(A, B).

Интуитивно trav(Left, L1) говорит, что нужно пройти по левому поддереву, сохраняя каждый элемент в L1. trav(Right, L2) говорит, что пройти по правому поддереву, сохраняя каждый элемент в L2. Наконец, append(L1, L2, L) добавьте два списка, L1 and L2 в список L. Для листа trav(X, [X]) помещает X в одноэлементный список, если он не объединяется с node.

person Matt    schedule 07.06.2015
comment
Правильно ли останавливать его после того, как он напечатает первую строку, если да, то как и где вы размещаете разрез? 1 ?- trav(node(1,node(2,node(a,b))),L). L = [1, 2, a, b] ; L = [1, 2, node(a, b)] ; L = [1, node(2, node(a, b))] ; L = [node(1, node(2, node(a, b)))]. - person Zast; 07.06.2015
comment
Можно ли явно аннотировать листья дерева? Итак, ваш запрос будет выглядеть примерно так: trav(node(leaf(1),node(leaf(2),node(leaf(a),leaf(b)))),L). В моем отредактированном ответе будет только одно решение. - person Matt; 07.06.2015
comment
Мы будем использовать приведенные выше примеры! - person Zast; 07.06.2015
comment
ОК @ user3633383, это должно сработать - person Matt; 07.06.2015