prolog

Question

我的请求与我在 Whosebug 上看到的不同。假设我的二叉树的形式是 tree(Node, Leafs)。没有左叶或右叶，只有属性 leafs.

你会如何计算那棵树中的节点？[=13=]

例如树可以是：

tree(node1, [tree(node2)]), tree(node3, []), tree(node4, [tree(node6,[tree(node2,[])]).

Answer 1

一个无序二叉树是一种树，每个节点最多可以有两个children，但是children之间的顺序并不重要。因此，non-empty 无序二叉树中的每个节点都可以表示为 tree(Node,Children) 形式的项，其中 Children 是空集（如果 Node 是叶子），或一组一棵或两棵树（如果 Node 是一个内部节点）。一个空的无序树可以表示为nil。为了简化实现，我们可以将集合表示为列表。比如无序二叉树：

    a
   / \
  b   c
 / \  |
d   e f

可以表示为：

mytree(tree(a,
            [tree(b,
                  [tree(d,[]),
                   tree(e,[])]),
             tree(c,
                  [tree(f,[])])])).

要计算无序二叉树中的节点，我们可以使用maplist/3 and sum_list/2，如下所示：

count_nodes(nil, 0).
count_nodes(tree(_Root, Children), N) :-
    maplist(count_nodes, Children, Ns), % call count_nodes, recursively, for each child
    sum_list([1|Ns], N).                % add 1 to count the root

这里有一些例子：

?- count_nodes(nil, N).
N = 0.

?- count_nodes(tree(a,[]), N).
N = 1.

?- count_nodes(tree(a,[tree(b,[])]), N).
N = 2.

?- count_nodes(tree(a,[tree(b,[]),tree(c,[])]), N).
N = 3.

?- mytree(T), count_nodes(T, N).
T = tree(a, [tree(b, [tree(d, []), tree(e, [])]), tree(c, [tree(f, [])])]),
N = 6.

prolog - 二叉树中的计数节点

prolog - counting node in a binary tree