Пролог бинарного дерева поиска

Question

Я столкнулся с этой проблемой:

Напишите программу PROLOG, в которой задано двоичное дерево с целыми числами, хранящимися в узлах. Напишите программу, которая возвращает максимальное значение, хранящееся в дереве. Например, учитывая вход [4,[1,[],[]],[7,[],[]]] алгоритм должен вернуться 7,

Я думаю, что я должен использовать BFS. Итак, это мои лекционные заметки о BFS:

bf(X,Y), Y список, содержащий элементы дерева X, которые встречаются при первом посещении в ширину.

bf([], []).
bf([void | Rest], Y):- bf(Rest, Y).
bf([tree(Integer, Right, Left) | Rest], [Integer | Y]) :- 
    append(Rest, [Left, Right], Nodes), 
    bf(Nodes, Y).

Я даже не знаю, что означают все переменные... Хотелось бы помочь.

Answer 1

Хорошо, bf/2 Предикат, который вы показываете, хорош и хорош, кроме описания должно было

bf( [X], Y): Y список, содержащий элементы дерева X, как встречается в первом порядке обхода дерева.

Здесь снова, с некоторыми более длинными, описательными именами переменных (я обычно предпочитаю очень короткие, даже однобуквенные имена, с описанием в комментариях, если это необходимо; вы, вероятно, сделаете это тоже позже, когда вам будет удобнее с Prolog) и некоторые подразумеваемые объединения, превращенные в явные объединения:

bf(Queue, Integers) :- 
    Queue    = [],                     %% breadth-first enumeration of the empty queue
    Integers = [].                     %% is the empty list

bf([HeadOfQueue | RestOfQueue], Integers):- 
    HeadOfQueue = void,                %% empty tree in the queue,
    bf(RestOfQueue, Integers).         %% go on with the same Integers list to fill

bf([HeadOfQueue | RestOfQueue], Integers) :- 
    HeadOfQueue = tree(Integer, Right, Left),            %% a tree in the queue,
    Integers = [Integer | MoreIntegers],                 %% fill the list's head
    append(RestOfQueue, [Left, Right], ExtendedQueue),   %% extend the popped queue
                                                         %%   with Left, then Right,
    bf(ExtendedQueue, MoreIntegers).                     %% and keep going

Он выталкивает узел из очереди "повестки дня", извлекает целое число узла, помещает его в список результатов, построенный сверху вниз, добавляет два дочерних узла узла в конец повестки дня и выполняет рекурсивные операции. Таким образом, это должно быть вызвано с [Tree] в качестве начальной очереди. Таким образом, деревья рассматриваются в порядке FIFO, достигая перечисления дерева в ширину. ЛИФО получит нас первыми.

Остается только то, над какими деревьями можно работать? Ответ прямо в коде: это составные термины формы

    tree( Int, RightChild, LeftChild )

где, очевидно, RightChild а также LeftChild должны быть деревьями / составными терминами одинаковой формы, или... вы это видите?... атом void, Скорее всего, это означает пустое дерево.

Деревья, которые вы показываете в своем примере, имеют другую структуру, [Int, LeftChild, RightChild] предположительно. Вам просто нужно настроить bf/2 предикат, чтобы соответствовать вашему новому ожидаемому формату данных.

Мы можем сделать это, сначала обобщив определение, абстрагируясь от специфики данных, с

bf([], []).                       %% implicit unifications, shorter names
bf([Empty | Rest], Y):- 
    empty(Empty),                                  %% data abstraction!
    bf(Rest, Y).
bf([Node | RestOfQueue], [Integer | Y]) :- 
    node(Node, Integer, Left, Right),              %% data abstraction!
    append(RestOfQueue, [Left, Right], ExtendedQueue), 
    bf(ExtendedQueue, Y).

empty( void ).
node( tree(Integer, Right, Left), Integer, Left, Right ).

Все, что осталось сделать сейчас, это переопределить empty/1 а также node/4 чтобы соответствовать вашему виду кодировки дерева. Это должно быть достаточно просто. Это прямо в вашем примере данных:

              [4,
                 [1, [], []],
                 [7, [], []]  ]

Так,

empty( ... ).
node( [ ..., ...., ... ] , ..., ..., ... ).

Сделав это, мы бы определили

maximum_element(Tree, MaxElem ):-
    bf( [Tree],  TreeElements ),
    list_maximum( TreeElements, MaxElem ).

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