递归计算k-ary树中的节点

Question

这不完全是家庭作业，但我需要在课堂上理解它。语言并不重要，伪代码就可以了。

编写“静态 K-ary”树类的递归成员函数，用于计算树中的节点数。

我想签名应该是这样的：

int countNodes(Node<AnyType> t, ctr, k){}

不知道怎么看k个孩子。在二叉树中，我会检查左右。谁能给我举个例子？

Answer 1

您可以将递归方程视为：

从一个节点开始的节点总数是1 + number of total children。然后可以找到节点总数如下：

def count(node):
    numOfNodes = 1
    for child in node.children:
        numOfNodes += count(child)
    return numOfNodes