Деревья в Прологе

Question

Я изучаю двоичные деревья в Прологе.

Я знаю структуру, но я не понимаю этот код в своих слайдах:

binary_tree(void).
binary_tree(tree(_Element,Left,Right)) :-
  binary_tree(Left), binary_tree(Right).

Это необходимо для распознавания древовидной структуры.

Но означает ли "void"?

Я попытался выполнить этот запрос

?- binary_tree(a).
false.

и предположить, что a - это один узел дерева.

Я просматриваю этот ресурс для понимания:

https://sites.google.com/site/prologsite/prolog-problems/4

, но отличается от моих слайдов.

Кто-нибудь может уточнить это?

Answer 1

void - это атом.Он не может принимать никаких значений (кроме себя).Кроме того, a, также атом, не является допустимым деревом в соответствии с определением вашего предиката.Дерево с a в качестве единственного узла будет представлено составным термином tree(a,void,void):

| ?- binary_tree(tree(a,void,void)).

yes

В качестве другого примера сбалансированное дерево с узлами a..g будет представлено термином (записаноотступ только для удобства чтения):

   tree(a,
       tree(b,
           tree(d,void,void),
           tree(e,void,void)
       ),
       tree(c,
           tree(f,void,void),
           tree(g,void,void)
       )
    )

Вы можете проверить, что этот термин снова является деревом, используя предикат binary_tree /1:

| ?- binary_tree(tree(a,tree(b,tree(d,void,void),tree(e,void,void)),tree(c,tree(f,void,void),tree(g,void,void)))).

yes