序言中的二叉树计数节点

Question

我构建了结构为 bt(Data,LeftTree,RightTree) 的二叉树。

btree(nil).
btree(bt(_,L,R)) :- btree(L), btree(R).

然后我想定义谓词 count1Child(Tree, Count) 断言 Count 是树中具有一个 child 的节点数。我知道如何计算树中节点的总数。但是不知道只有一个 child.

的计数节点

Answer 1

在开始编写谓词之前，让我们尝试定义一个谓词，为您要计算的节点提供 true，为那些仍可能出现但不会出现的节点提供 false数数。通过这种方式，我们也隐含地定义了我们想要的东西。我假设您只需要有两个子树的节点。

singlechild_t(nil, false).
singlechild_t(bt(_,nil,bt(_,_,_)), true).
singlechild_t(bt(_,bt(_,_,_),nil), true).
singlechild_t(bt(_,nil,nil), false).
singlechild_t(bt(_,bt(_,_,_),bt(_,_,_)), false).


tree_count(P_2, T, N) :-
   tree_count(P_2, T, 0,N).

tree_count(_, nil, N,N).
tree_count(P_2, T, N0,N) :-
   T = bt(_,L,R),
   if_(call(P_2, T), A = 1, A = 0),
   N1 is N0+A,
   tree_count(P_2, L, N1,N2),
   tree_count(P_2, R, N2,N).

 tree_countsingles(T, N) :-
    tree_count(singlechild_t, T, N).

（使用 if_/3）

Answer 2

cbt(nil, 0).
cbt(bt(_,L,R), T) :- cbt(L,Nl),cbt(R,Nr),
    ( (L=nil,R\=nil ; L\=nil,R=nil) -> C = 1 ; C = 0 ),
    T is Nl + Nr + C.

但是你在问题中给出的测试树似乎无效：我用

测试过

?- cbt(bt(1,bt(2,nil,bt(3,nil,nil)),nil),N).
N = 2.

序言中的二叉树计数节点

Binary Tree counting nodes in prolog

prolog