recursion - k-ary ツリーのノードを再帰的にカウントする

Question

これは正確には宿題ではありませんが、授業のために理解する必要があります。言語は特に問題ではありません。疑似コードで問題ありません。

ツリー内のノード数をカウントする「静的 K-ary」ツリークラスの再帰メンバー関数を記述します。

署名は次のようになると思います。

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

私はk人の子供たちを見る方法がわかりません。二分木では、左と右をチェックします。誰かが私にこれの例を教えてもらえますか?

score 6 · Accepted Answer

再帰方程式は次のように考えることができます。

ノードから始まるノードの総数はです1 + number of total children。次に、ノードの総数は次のように求めることができます。

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

score 2 · Accepted Answer

擬似コード:

count(r)
    result = 1
    for each child node k
        result = result + count(k)
    return result

2 に答える 2