Prolog-检查两棵二元树是否等效
我想知道如何检查SWI-Promog中的两棵二元树是否等效。
我尝试过：
equivalent(nil, nil).
equivalent(t(N,L1,R1), t(N,L2,R2)):- equivalent(L1,L2), equivalent(R1,R2).
但是它不起作用。
I would like to know how to check if two binary trees are equivalent in SWI-Prolog.
I tried:
equivalent(nil, nil).
equivalent(t(N,L1,R1), t(N,L2,R2)):- equivalent(L1,L2), equivalent(R1,R2).
but it does not work.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我认为，通过“等价”，您的意思是，如果两个树都包含相同的有序数据节点集，则可能具有不同的根节点。
要测试这种等效性，也需要：
以并联和深度优先遍历树木，并比较每个节点，或者
我建议后一种方法，因为实现要简单得多。
给定二进制树
t（有效载荷，left_children，right_children）其中atomnil指示空树，将二进制树扁平到链接列表中很容易：比较两棵树的等效性很容易，就像
两棵树都将两棵树弄平到同一列表中一样。
另一个，也许更简单/更多的表现方法来扁平的二进制树使用谓词，该谓词按顺序访问每个节点并使用
findall/3将其合并到列表中。访问节点的顺序很容易。从根节点开始，
类似的东西：
I assume that by "equivalence", you mean that two trees are equivalent if they each contain the same ordered set of data nodes, with possibly different root nodes.
To test for that sort of equivalence requires either:
Traversing the trees in parallel and depth-first and comparing each node, or
Flattening each tree into an ordered list (the worst-case, degenerate form of a binary tree, where the nodes are inserted in order), and then comparing the two lists.
I would suggest the latter approach, because the implementation is much simpler.
Given a binary tree
t(Payload,Left_Children,Right_Children)where the atomnilindicates the empty tree, flattening a binary tree into a linked list is as easy as this:And comparing two trees for equivalence is as easy as
The two trees are equivalent if the both flatten into the same list.
Another, perhaps simpler/more performant method of flattening a binary tree uses a predicate that visits each node in order and uses
findall/3to coalesce that into a list.Visiting nodes in order is easy. Beginning with the root node,
Something like this: