在Prolog中如何实现width_tree谓词计算二叉树的宽度

要计算二叉树同层节点最大数量（即宽度），采用层序遍历（广度优先遍历）的思路实现最直接，按层统计节点数后取最大值即可，无需单独拆分左右子树统计。

完整实现代码 #

% 边界条件：空树宽度为0
width_tree(nil, 0) :- !.

% 主谓词：传入树结构，返回宽度
width_tree(Tree, Result) :-
    % 初始第一层只有根节点，初始最大宽度为0，调用辅助谓词遍历
    bfs_width([Tree], 0, Result).

% 辅助谓词：层序遍历计算最大宽度
% 终止条件：当前层无节点，返回累计的最大宽度
bfs_width([], Max, Max) :- !.
bfs_width(CurrLevel, CurrMax, Result) :-
    % 统计当前层节点数量
    length(CurrLevel, LevelWidth),
    % 更新最大宽度
    NewMax is max(CurrMax, LevelWidth),
    % 生成下一层所有非nil的子节点列表
    get_next_level(CurrLevel, NextLevel),
    % 递归处理下一层
    bfs_width(NextLevel, NewMax, Result).

% 辅助谓词：根据当前层节点生成下一层子节点列表
get_next_level([], []) :- !.
get_next_level([nil|Rest], NextLevel) :-
    get_next_level(Rest, NextLevel), !.
get_next_level([[_, Left, Right]|Rest], NextLevel) :-
    get_next_level(Rest, RestNext),
    % 过滤nil节点，将有效子节点加入下一层列表
    append_valid_child(Left, RestNext, Temp),
    append_valid_child(Right, Temp, NextLevel).

% 工具谓词：仅将非nil的节点加入列表
append_valid_child(nil, List, List) :- !.
append_valid_child(Node, List, [Node|List]).

测试验证 #

你提供的测试二叉树调用方式如下：

?- width_tree([12, [8, [5, [2, nil, nil], nil],[11, nil, nil]], [65, [42, nil, nil], [99, nil, nil]]], Result).

执行后返回 Result = 4，和预期结果一致。

原代码问题说明 #

你之前的思路单独处理左右子树，需要额外维护左右子树各层的节点数再对应求和，逻辑复杂度更高。层序遍历的方案直接按整层处理节点，天然就可以直接统计每层的总节点数，实现更简洁不易出错。

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