prolog - 如何使用 Prolog 查找二叉树的深度

Question

我正在学习 Prolog，并尝试使用 Prolog 查找二叉树的深度。我代表一棵这样的树:

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.

我想要一个深度谓词，如果 N 是树 T 的深度，则深度(T，N)将为真。我假设当 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 成为 2 个子树之间的最大值。

感谢您的帮助。

解决方案:

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).

对于树情况，在两个分支上递归调用深度/2并max它们:

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