Как найти глубину бинарного дерева с помощью пролога

Question

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

nil is a tree.
tree(1,nil,nil) this is a leaf.
tree(1,tree(1,nil,nil),nil) this is a tree with root 1 and has a left leaf 1.

Я хочу предикат глубины той глубины (T, N), которая будет истинной, если N - это глубина дерева T. Я предполагаю, что я буду использоватьПредикат глубины, когда T не является переменной, но N может быть переменной. Примеры:

?- depth(nil,N).
N = 0.

?- depth(tree(1,tree(2,nil,tree(3,nil,nil)),tree(5,tree(6,nil,nil),nil)),N).
N = 3.

?- depth(tree(1,nil,tree(2,nil,nil)),N).
N = 2.

Я не уверен, как сделать так, чтобы N было максимумом между двумя поддеревьями.

Спасибо за любую помощь.

Решение:

depth(nil,0).
depth(tree(_,nil,nil),1).
depth(tree(_,Left,Right), D) :- 
    depth(Left,DLeft),
    depth(Right,DRight),
    D is max(DLeft, DRight) + 1.

Answer 1

Легко, как пирог: глубина nil равна 0:

depth(nil,0).

Для случая tree, рекурсивно вызвать depth/2 в обеих ветвях и max их:

depth(Left,DLeft),
depth(Right,DRight),
D is max(DLeft, DRight) + 1.

Answer 2

% I added Root \= nil, simulating a null node and it works

depth_tree(nil, 0).

depth_tree(node(Root, Left, Right), Depth):- 

      Root\= nil, 

      depth_tree(Left, DepthLeft),

      depth_tree(Right, DepthRight),

      Depth is max(DepthLeft, DepthRight) + 1.