Пролог для подсчета всех листовых узлов в двоичном дереве - PullRequest
Новая
       14

Пролог для подсчета всех листовых узлов в двоичном дереве

0 голосов
/ 26 октября 2018

Мне нужно сосчитать все внутренние узлы двоичного дерева с помощью пролога. Я могу сосчитать все узлы, используя следующий код 

internal(tree(_,L,R), I) :- internal(L, I2), internal(R, I3), I is I2 + I3 + 1.
internal(nil, 0).

И я подумал, что изменив базовый вариант на 

internal(tree(_,nil, nil), 0).

Я мог бы заставить его работать, но он возвращает false.

вот тестовый пример, который должен вернуть 4 внутренних (дерево (8, дерево (5, дерево (2, ноль, ноль)), дерево (7, ноль, ноль)), дерево (9, ноль, дерево (15, дерево (11, ноль, ноль), ноль))), я).

Может кто-нибудь сказать мне, где мойошибка есть?Спасибо

После прочтения ваших предложений я получил это, но все равно не получается. 

internal(tree(_,L,R), I) :- internal(L, I2), internal(R, I3), I is I2 + I3. 
internal(tree(_,nil, R), I):- !, internal(R, I3), I is I3 + 1. 
internal(tree(_,L, nil), I):- !, internal(L, I3), I is I3 + 1.
internal(tree(_,nil, nil), 0).
internal(nil, 0).

1 Ответ

0 голосов
/ 26 октября 2018

Если вы измените предикат на: 

internal(tree(_,nil, nil), 0).
internal(tree(_,L,R), I) :- internal(L, I2), internal(R, I3), I is I2 + I3 + 1.

, тогда это не удастся для деревьев с nil потомком и не-1005 * потомком. Это не удастся.

Действительно: если дерево tree(1, nil, tree(2, nil, nil)), то Пролог сначала попытается удовлетворить базовый случай, но синус nil не равен tree(_, nil, nil), что не удается. Затем он стремится удовлетворить рекурсивный случай и сначала объединяет L = nil и R = tree(2, nil, nil). Теперь он вызывает internal(L, I2), но, поскольку internal(nil, I1) не может быть удовлетворен, он терпит неудачу.

Таким образом, мы можем сначала построить предикат, который удовлетворяет, если два поддерева приводят к внутреннему узлу: 

isinternal(tree(_, _, _), _).
isinternal(_, tree(_, _, _)).

поэтому этот предикат завершается успешно, если хотя бы одно из поддеревьев имеет значение tree(_, _, _).. Теперь мы можем использовать этот предикат для подсчета количества внутренних узлов: 

internal(nil, 0).
internal(tree(_, nil, nil), 0).
internal(tree(_, L, R), I) :-
    isinternal(L, R),
    internal(L, NL),
    internal(R, NR),
    I is NL + NR + 1.

Выше можно улучшить с точки зрения читабельности. Я оставляю это как упражнение.

...