Prolog树高度计算：如何让查询仅返回整棵树的高度？

问题背景 #

已定义合法树的tree/1谓词（代码已验证正确）：

tree(X) :- const(X).
tree(X) :- variable(X).
tree(f(T1,T2)) :- tree(T1), tree(T2).
tree(g(T)) :- tree(T).
tree(h(T1,T2,T3)) :- tree(T1),tree(T2),tree(T3).
const(a).
const(b).
const(c).
variable(vX).
variable(vY).
variable(vZ).

当前实现的height/2谓词用于计算树的高度，但查询时会返回所有中间高度值（比如高度为2的树会返回0、1、2），代码如下：

height(c,0).
height(X,0).
height(f(T1,T2),N) :- height(T1, N1), height(T2, N2), N is max(N1, N2)+ 1.
height(g(T), N) :- height(T, N1), N is N1 + 1.
height(h(T1, T2, T3), N) :- height(T1, N1), height(T2, N2), height(T3, N3), N23 is max(N2, N3), N is max(N1, N23) + 1.

需求：修改height/2，使查询仅返回整棵树的高度，而非所有中间值。

问题原因 #

当前height(X,0)是无约束的匹配规则，任何未被前面规则匹配的项都会触发这条规则，导致递归过程中每个叶子节点（常量、变量）返回高度0，同时递归路径上的中间节点也会返回各自的高度，最终查询会枚举所有可能的高度值。此外，单独的height(c,0)规则属于冗余定义，常量本身已被归为叶子节点范畴。

解决方案 #

修改height/2规则，明确区分叶子节点和非叶子节点，避免无约束匹配：

% 叶子节点：常量或变量，高度固定为0
height(X, 0) :- const(X); variable(X).

% 函子f/2的高度：取两个子树高度的最大值加1
height(f(T1,T2), N) :-
    height(T1, N1),
    height(T2, N2),
    N is max(N1, N2) + 1.

% 函子g/1的高度：子树高度加1
height(g(T), N) :-
    height(T, N1),
    N is N1 + 1.

% 函子h/3的高度：取三个子树高度的最大值加1
height(h(T1,T2,T3), N) :-
    height(T1, N1),
    height(T2, N2),
    height(T3, N3),
    MaxSub is max(max(N1, N2), N3),
    N is MaxSub + 1.

验证示例 #

查询整棵树的高度：

?- height(f(g(a), b), Z).

此时仅返回Z = 2，符合预期。

若需确保输入是合法树，可结合tree/1谓词验证：

?- tree(f(g(a), b)), height(f(g(a), b), Z).

内容的提问来源于stack exchange，提问作者Dorhana