使用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;
}

Output

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

上述代码的解释

在这种方法中，我们应用BFS（广度优先搜索）或层次遍历，并检查每个节点的子节点数量。然后，将该数量的阶乘乘以我们的答案。

结论

本教程介绍了几种遍历N叉树组合的方法，并应用了BFS。我们还学习了解决这个问题的C++程序和完整的方法。

我们可以用其他语言（如C、Java、Python和其他语言）编写相同的程序。希望你觉得这个教程有帮助。

以上是使用C++找到遍历N叉树的方式的数量的详细内容。更多信息请关注PHP中文网其他相关文章！