Prolog

Question

我想知道如何在 SWI-Prolog 中检查两个二叉树是否等价。

我试过了：

equivalent(nil, nil).
equivalent(t(N,L1,R1), t(N,L2,R2)):- equivalent(L1,L2), equivalent(R1,R2).

但是没用。

Answer 1

我假设“等价”是指如果两棵树都包含相同的有序数据节点集，并且可能具有不同的根节点，则它们是等价的。

要测试这种等价性，需要：

我建议采用后一种方法，因为实现起来要简单得多。

给定一棵二叉树 t(Payload,Left_Children,Right_Children)，其中原子 nil 表示空树，将二叉树展平为链表就像这样简单：

flatten( nil      , [] ) .
flatten( t(P,L,R) , Ps ) :-
  flatten(L,Ls),
  flatten(R,Rs),
  append(Ls,[P|Rs],Ps)
  .

比较两棵树的等价性就像

一样简单

equivalent(T1,T2) :- flatten(T1,L), flatten(T2,L) .

如果两个树都展平到同一个列表中，那么这两个树是等价的。

另一种可能 simpler/more 展平二叉树的高效方法使用谓词按顺序访问每个节点并使用 findall/3 将其合并到列表中。

按顺序访问节点很容易。从根节点开始，

像这样：

flatten(T,Ps) :- findall(P, visit(T,P), Ps ) .

visit( t(_,L,_) , P ) :- visit(L,P) .
visit( t(P,_,_) , P ) .
visit( t(_,_,R) , P ) :- visit(R,P) .

Prolog - 检查两个二叉树是否等价