Найти элемент в двоичном дереве в PROLOG - PullRequest
Новая
       20

Найти элемент в двоичном дереве в PROLOG

0 голосов
/ 19 декабря 2018

Я пытаюсь реализовать это с помощью Пролога, чтобы найти элемент в двоичном дереве. 

elem1(tree(Element,void,void),Element).

elem1(tree(_Element,Left,Right),N) :-
  elem1(Left,N), 
  elem1(Right,N).

, потому что я думаю, что elem1 проверяет, является ли корень моего дерева элементом, который я ищу, и этоработать с этим выводом. 

?- trace,elem1(tree(c,void,void),c).
Call: (9) elem1(tree(c, void, void), c) ? creep
Exit: (9) elem1(tree(c, void, void), c) ? creep
true

Но рекурсивным способом, подобным этому: 

  ?- trace,elem1(tree(4,tree(1,void,void),tree(2,void,void)),1).
  Call: (9) elem1(tree(4, tree(1, void, void), tree(2, void, void)), 1) 
  creep
  Call: (10) elem1(tree(1, void, void), 1) ? creep
  Exit: (10) elem1(tree(1, void, void), 1) ? creep
  Call: (10) elem1(tree(2, void, void), 1) ? creep
  Call: (11) elem1(void, 1) ? creep
  Fail: (11) elem1(void, 1) ? creep
  Fail: (10) elem1(tree(2, void, void), 1) ? creep
  Redo: (10) elem1(tree(1, void, void), 1) ? creep
  Call: (11) elem1(void, 1) ? creep
  Fail: (11) elem1(void, 1) ? creep
  Fail: (10) elem1(tree(1, void, void), 1) ? creep
  Fail: (9) elem1(tree(4, tree(1, void, void), tree(2, void, void)), 1) ? 
  creep

  false.

кажется, что правильно вызовите (10) и проверьте правильность предиката, но после tryрасширить больше и дать мне неудачу.

Я не знаю, почему это произошло, но базовый случай работает хорошо, поэтому я обращаю внимание на то, что когда найду элемент, выйдите и дайте мне истину, потому что базовый предикат действителен.

1 Ответ

0 голосов
/ 19 декабря 2018

Ваш код немного изменен, чтобы показать использование преувеличенного AND (,). 

elem_01(tree(Element,void,void),Element).

elem_01(tree(_Element,Left,Right),N) :-
  (
    elem_01(Left,N)
  ,
    elem_01(Right,N)
  ).

Пример: 

?- elem_01(tree(4,tree(1,void,void),tree(2,void,void)),1).
false.

, который дает неверный результат.

Исправленная версия, которая использует OR (;). 

elem_02(tree(Element,void,void),Element).

elem_02(tree(_Element,Left,Right),N) :-
  (
    elem_02(Left,N)
  ;
    elem_02(Right,N)
  ).

Пример: 

?- elem_02(tree(4,tree(1,void,void),tree(2,void,void)),1).
true ;
false.

Правильно находит 1 в двоичном дереве. 

?- elem_02(tree(4,tree(1,void,void),tree(2,void,void)),3).
false.

Правильно показывает3 отсутствует в дереве.

Исправленная версия для отображения использования двух предложений вместо ИЛИ (;). 

elem_03(tree(Element,void,void),Element).

elem_03(tree(_Element,Left,_),N) :-
    elem_02(Left,N).

elem_03(tree(_Element,_,Right),N) :-
    elem_02(Right,N).

Пример: 

?- elem_03(tree(4,tree(1,void,void),tree(2,void,void)),1).
true ;
false.

Правильно находит 1 в двоичном дереве. 

?- elem_03(tree(4,tree(1,void,void),tree(2,void,void)),3).
false.

Правильно показывает, что 3 отсутствует в дереве.

В своем вопросе вы отображаете дерево как 

elem1(tree(4,tree(1,void,void),tree(2,void,void)),1).

например, 

  4
 / \
1   2

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

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

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

Это правильное дерево дляваш пример: 

elem1(tree(2,tree(1,void,void),tree(4,void,void)),1).

например 

  2
 / \
1   4
...