在 Prolog 中查找二叉树的高度

Question

所以我的任务是使用以下事实创建二叉树，这些事实定义每个节点及其两个 child 节点：

node(root, a, b).
node(a, c, d).
node(b, z, y).
node(c, e, f).
node(d, x, w).
node(e, g, h).
node(z, v, u).
node(u, t, s).
node(t, r, q).

我想定义规则height(RootNode, Height)来计算二叉树的高度从 RootNode 开始。树的高度是距离最长的距离（节点数）根节点到最远的叶节点。叶节点是一个没有任何 child仁。一个叶子节点的高度为1.

我目前的代码是：

node(root, a, b).
node(a, c, d).
node(b, z, y).
node(c, e, f).
node(d, x, w).
node(e, g, h).
node(z, v, u).
node(u, t, s).
node(t, r, q).

height(nil, 0).
height(RootNode, Height):-
    node(RootNode, Left, Right),
    height(Left, LH),
    height(Right, RH),
    Height is max(LH, RH) + 1.

此刻，我真的被困住了，很想知道这段代码在运行时会发生什么，为什么我做错了，我应该在哪里进一步改进？感谢任何帮助。

Answer 1

您的代码的问题是您的基本情况要求每个叶节点以 node(Leaf, nil, nil) 的形式存在于数据库中，但根据您的示例，叶节点只是作为第二个或第三个参数出现的节点node/3 个事实，但没有作为另一个 node/3 个事实的第一个参数出现。

因此，您可以通过更改基本案例来修复代码：

而不是

height(nil, 0).

使用

height(Leaf, 1):-
  \+node(Leaf, _, _).

（请注意，根据您的描述，基本案例的高度为 1）

测试用例：

?- height(root,A).
A = 6 ;
false.

您也可以将两个子句“合并”在一个子句中：

height(RootNode, Height):-
    node(RootNode, Left, Right) *->
    (height(Left, LH),
    height(Right, RH),
    Height is max(LH, RH) + 1) ; Height = 1.

测试运行:

?- height(root,A).
A = 6.

在 Prolog 中查找二叉树的高度

Finding the binary tree height in Prolog

recursion

binary-tree

prolog