C++を使用してN-aryツリーをトラバースする方法の数を見つける

N-aryツリーが与えられ、このツリーをトラバースする方法の総数を見つける必要があります。たとえば、-

上記のツリーの場合、出力は192になります。

この問題については、組み合わせ論についての知識が必要です。この問題では、すべてのパスで可能なすべての組み合わせを確認するだけで、答えが得られます。

解決策を見つけるためのアプローチ

このアプローチでは、レベル順トラバーサルを実行し、各ノードの子の数を確認してから、階乗を答えに乗算するだけです。

例

上記のアプローチのC++コード

#include<bits/stdc++.h>
using namespace std;
struct Node{ // structure of our node
    char key;
    vector<Node *> child;
};
Node *createNode(int key){ // function to initialize a new node
    Node *temp = new Node;
    temp->key = key;
    return temp;
}
long long fact(int n){
    if(n <= 1)
        return 1;
    return n * fact(n-1);
}
int main(){
    Node *root = createNode('A');
    (root->child).push_back(createNode('B'));
    (root->child).push_back(createNode('F'));
    (root->child).push_back(createNode('D'));
    (root->child).push_back(createNode('E'));
    (root->child[2]->child).push_back(createNode('K'));
    (root->child[1]->child).push_back(createNode('J'));
    (root->child[3]->child).push_back(createNode('G'));
    (root->child[0]->child).push_back(createNode('C'));
    (root->child[2]->child).push_back(createNode('H'));
    (root->child[1]->child).push_back(createNode('I'));
    (root->child[2]->child[0]->child).push_back(createNode('N'));
    (root->child[2]->child[0]->child).push_back(createNode('M'));
    (root->child[1]->child[1]->child).push_back(createNode('L'));
    queue<Node*> q;
    q.push(root);
    long long ans = 1;
    while(!q.empty()){
        auto z = q.front();
        q.pop();
        ans *= fact(z -> child.size());
        cout << z->child.size() << " ";
        for(auto x : z -> child)
           q.push(x);
   }
   cout << ans << "\n";
   return 0;
}

出力

4 1 2 2 1 0 0 1 2 0 0 0 0 0 192

上記のコードの説明

このアプローチでは、BFS（幅優先探索）またはレベル順序トラバーサルを適用し、各ノードの子の数を確認します。次に、その数の階乗を私たちの答えに掛けます。

結論

このチュートリアルでは、N-aryツリーの組み合わせ論をトラバースする方法とBFSを適用する方法をいくつか紹介します。また、この問題のC++プログラムと解決した完全なアプローチについても学びました。

同じプログラムを、C、java、python、その他の言語などの他の言語で作成できます。このチュートリアルがお役に立てば幸いです。