Prolog实现二叉树指定元素深度查询 代码问题排查

问题背景 #

需要实现Prolog谓词计算无重复元素二叉树中给定元素E的深度，二叉树节点结构约定为t(节点值, 左子树, 右子树)，nil表示空节点，约定根节点深度为1。原有实现代码无法正常运行，需要排查问题并给出正确方案。
原有错误代码如下：

ElemDepth(E,t(E,T1,T2), D).
ElemDepth(E,t(M,T1,T2), D):- D1 is D+1, ElemDepth(E,T1, D1).
ElemDepth(E,t(M,T1,T2), D):- D1 is D+1, ElemDepth(E,T2, D1).

原代码问题排查 #

原代码存在三个核心错误导致无法运行：

• 终止子句未绑定深度变量：匹配到存储目标元素E的节点时，没有为深度参数D赋值，变量无确定绑定值，无法返回正确结果。
• 变量实例化顺序错误：D1 is D+1的计算要求D必须是已绑定的数值，但常规查询场景下用户会传入未绑定的D期望获得深度结果，首次进入递归子句时D完全未实例化，会触发is/2的参数未实例化错误。
• 缺少节点值判断：递归子句中没有明确当前节点值M不等于目标E，会产生大量无意义的回溯路径，降低运行效率。

正确实现方案 #

基础递归版本（无需额外参数，直接调用即可） #

逻辑为：若当前节点是目标节点，深度为1；若目标在左/右子树中，当前节点深度为子树返回的深度值加1。

% 匹配到目标节点，当前层深度基准为1
elem_depth(E, t(E, _, _), 1).
% 递归查找左子树
elem_depth(E, t(M, Left, _), D) :-
    E \= M,
    elem_depth(E, Left, DLeft),
    D is DLeft + 1.
% 递归查找右子树
elem_depth(E, t(M, _, Right), D) :-
    E \= M,
    elem_depth(E, Right, DRight),
    D is DRight + 1.

尾递归优化版本（累加器实现，大深度树性能更优） #

通过累加器从根节点向下传递当前深度，匹配到目标时直接返回当前深度值，属于尾递归结构，不会产生递归栈堆叠。

% 对外调用入口，自动传入根节点初始深度1
elem_depth(E, Tree, D) :-
    elem_depth_acc(E, Tree, 1, D).

% 匹配到目标节点，直接返回累计的深度值
elem_depth_acc(E, t(E, _, _), CurrentD, CurrentD).
% 向左子树递归，深度+1
elem_depth_acc(E, t(M, Left, _), CurrentD, ResultD) :-
    E \= M,
    NextD is CurrentD + 1,
    elem_depth_acc(E, Left, NextD, ResultD).
% 向右子树递归，深度+1
elem_depth_acc(E, t(M, _, Right), CurrentD, ResultD) :-
    E \= M,
    NextD is CurrentD + 1,
    elem_depth_acc(E, Right, NextD, ResultD).

调用示例 #

对于如下结构的二叉树：

1
   / \
  2   3
 /
4

对应的Prolog树结构定义为：
T = t(1, t(2, t(4, nil, nil), nil), t(3, nil, nil))
查询结果：

• 执行elem_depth(1, T, D)，返回D = 1
• 执行elem_depth(3, T, D)，返回D = 2
• 执行elem_depth(4, T, D)，返回D = 3
• 查找不存在的元素，如elem_depth(5, T, D)，谓词直接返回false，符合预期。

如果需要将根节点深度约定为0，只需要将基础版本终止子句的1改为0，或者将累加器版本的初始传入深度从1改为0即可。

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