C++ を使用して N 分ツリーを走査する方法の数を求めます。

N 分ツリーが与えられた場合、私たちのタスクは、ツリーを横断する方法の合計数を見つけることです。たとえば、 -

上記のツリーの場合、出力は次のようになります。 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(&#39;A&#39;);
    (root->child).push_back(createNode(&#39;B&#39;));
    (root->child).push_back(createNode(&#39;F&#39;));
    (root->child).push_back(createNode(&#39;D&#39;));
    (root->child).push_back(createNode(&#39;E&#39;));
    (root->child[2]->child).push_back(createNode(&#39;K&#39;));
    (root->child[1]->child).push_back(createNode(&#39;J&#39;));
    (root->child[3]->child).push_back(createNode(&#39;G&#39;));
    (root->child[0]->child).push_back(createNode(&#39;C&#39;));
    (root->child[2]->child).push_back(createNode(&#39;H&#39;));
    (root->child[1]->child).push_back(createNode(&#39;I&#39;));
    (root->child[2]->child[0]->child).push_back(createNode(&#39;N&#39;));
    (root->child[2]->child[0]->child).push_back(createNode(&#39;M&#39;));
    (root->child[1]->child[1]->child).push_back(createNode(&#39;L&#39;));
    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

上記コードの説明

In この方法では、BFS (Breadth First Search) または階層トラバーサルを適用し、各ノードの子の数を確認します。次に、その量の階乗と答えを掛けます。

結論

このチュートリアルでは、N 分木の組み合わせを走査するいくつかの方法を紹介し、BFS を適用します。また、C プログラムとこの問題を解決するための完全な方法も学びました。

同じプログラムを、C、Java、Python などの他の言語で書くことができます。このチュートリアルがお役に立てば幸いです。

以上がC++ を使用して N 分ツリーを走査する方法の数を求めます。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。