二叉树同构

Question

除其他事项外，我还有一个任务要写，一组prolog谓词，用于确定任何两棵二叉树是否是同构的。谓词还必须能够将所有同构图提供给任何给定的二叉树。

到目前为止，这是我所拥有的，除了返回副本外，它是有效的。

% Clause: btree_iso
%
% Specification:
% --------------
% Satisfied when the two binary-tree parameters are isomorphic. Two binary
% trees are isomorphic if one can be derived from the other by changing the
% order of the branches. Either of the parameters may be instantiated with a
% variable when btree_iso is used in a top-level goal.
%
% Description:
% ------------
% Base case for the binary tree iso morphism predicate.
% Both sides are leaves.
btree_iso( leaf, leaf ).

% Description:
% ------------
% TODO
btree_iso( node( BTL1, X, BTR1 ), node( BTL2, X, BTR2 ) ) :- btree_iso( BTL1, BTL2 ),
                                                             btree_iso( BTR1, BTR2 ).
% Description:
% ------------
% TODO
btree_iso( node( BTL1, X, BTR1 ), node( BTL2, X, BTR2 ) ) :- btree_iso( BTL1, BTR2 ),
                                                             btree_iso( BTR1, BTL2 ).

预期输出：

? - btree_iso(node(node(leaf,3,leaf),3,node(leaf,5,leaf)),BT).
BT = node(node(leaf, 3, leaf), 3, node(leaf, 5, leaf)) ;
BT = node(node(leaf, 5, leaf), 3, node(leaf, 3, leaf)).

我的输出

?- btree_iso(node(node(leaf,3,leaf),3,node(leaf,5,leaf)),BT).
BT = node(node(leaf, 3, leaf), 3, node(leaf, 5, leaf)) ;
BT = node(node(leaf, 3, leaf), 3, node(leaf, 5, leaf)) ;
BT = node(node(leaf, 3, leaf), 3, node(leaf, 5, leaf)) ;
BT = node(node(leaf, 3, leaf), 3, node(leaf, 5, leaf)) ;
BT = node(node(leaf, 5, leaf), 3, node(leaf, 3, leaf)) ;
BT = node(node(leaf, 5, leaf), 3, node(leaf, 3, leaf)) ;
BT = node(node(leaf, 5, leaf), 3, node(leaf, 3, leaf)) ;
BT = node(node(leaf, 5, leaf), 3, node(leaf, 3, leaf)).

显然，这些都是重复的，我似乎找不到合适的位置放置裁剪，这样谓词就不会返回重复项。我还尝试为只有一个叶的节点和另一个节点编写另外两个谓词，但它们似乎没有帮助。

有什么建议告诉我怎样才能阻止这些副本吗？

Answer 1

想想BT =节点(叶，X，叶)时会发生什么。对于这种情况，您的解决方案产生两个相同的解决方案。一种是树叶交换的地方，另一种是它们不是的地方。

您需要显式地处理这种情况，只返回一个解决方案。由于这种情况可能类似于其他子句，所以您还需要确保这种情况不能被多个子句所满足。