Пролог бинарного дерева поиска - PullRequest
0 голосов
/ 03 июня 2018

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

Напишите программу 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).

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

1 Ответ

0 голосов
/ 03 июня 2018

ОК, показанный вами предикат 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 ).

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...