Count the nodes of a multiway tree

题目

Write a predicate nnodes/1 which counts the nodes of a given multiway tree. Example: ?- nnodes(t(a,[t(f,[])]),N). N = 2

Write another version of the predicate that allows for a flow pattern (o,i).

用单元测试描述为：

解题思路

多路树是一个递归定义的结构，所以用递归算法来统计节点数是最自然的了。

1. 首先统计根节点
2. 分别统计每棵子树的节点数（子树都是多路树，所以这𥚃直接套用步骤1至3）
3. 合计所有子树的节点数加根节点

举个例子，有多路树(a,[(b,[(c,[]),(d,[])])])。

• 先统计根节点为1
• 再统计每一棵子树，这𥚃有一棵子树(b,[(c,[]),(d,[])])
  • 先统计根节点数为1
  • 再统计每一棵子树，这𥚃有两棵子树(c,[]),(d,[])
    • 针对(c,[])，先统计根节点为1，其没有子树。所以整棵子树的节点数为1
    • 针对(d,[])，先统计根节点为1，其没有子树。所以整棵子树的节点数为1
  • 合计所有子树的节点数和自身根节点数，1+1=1=3。本子树的节点縂数为3
• 合计所有子树的节点数再加上自身根节点数，3+1=4。縂计4个节点

代码实现：

reduce是Python标准库提供的一个函数式的工具，其声明为：

reduce(function, iterable, initializer)

其功能是将function累积地、从左往右作用于iterable中的每一个元素。

reduce相当于如下代码：

def reduce(function, iterable, initializer=None):
    it = iter(iterable)
    if initializer is None:
        value = next(it)
    else:
        value = initializer
    for element in it:
        value = function(value, element)
    return value

这𥚃我们使用reduce实现累加的功能。其将所有子树节点数累加起来，本身节点数1以initializer的形式被累加进来。