Prolog实现construct()函数从列表构建二叉树的问题咨询

现有代码核心问题 #

• 语法逻辑错误：Prolog 是逻辑编程语言，没有函数返回值的概念，你不能直接把construct(T,R)写在tree的参数位置，必须先通过谓词调用把递归生成的子树绑定到变量，再把变量放到tree的对应参数中
• 参数类型不匹配：第二个子句construct(E, tree(E,nil,nil))的第一个入参是单个元素，但你的construct第一个参数设计为列表，单个元素的场景应该写为construct([E], tree(E,nil,nil))
• 比较逻辑错误：你直接拿列表T和头部元素H做大小比较，列表不能直接和数字比较，会直接报错
• 结构逻辑错误：你写的两个递归子句都把右子树写死为nil，根本不可能生成正常的左右子树结构，完全不符合二叉树的构建逻辑

实现思路 #

你确实需要用到辅助谓词：将单个元素插入到现有二叉搜索树的insert/3，之后construct递归遍历列表，逐个把元素插入到树中即可。

可运行实现代码 #

% 辅助谓词：插入元素E到二叉树中，返回新二叉树
insert(E, nil, tree(E, nil, nil)).
insert(E, tree(Root, Left, Right), tree(Root, NewLeft, Right)) :-
    E < Root,
    insert(E, Left, NewLeft).
insert(E, tree(Root, Left, Right), tree(Root, Left, NewRight)) :-
    E > Root,
    insert(E, Right, NewRight).

% 主谓词：从列表构建二叉搜索树
construct([], nil).
construct([H|T], ResultTree) :-
    construct(T, TempTree),
    insert(H, TempTree, ResultTree).

测试示例 #

查询construct([3,1,4,2], T)，返回符合预期的二叉树结构：
T = tree(2, tree(1, nil, tree(3, nil, tree(4, nil, nil))), nil)
如果需要调整元素插入顺序，修改递归的调用顺序即可。

内容的提问来源于stack exchange，提问作者Lobna Hisham Eldeeb