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

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( <b>[X]</b>, Y): Y - это список, содержащий элементы дерева X, как встречается в порядке обхода дерева в ширину.

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

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 ).

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