使用C++找到遍历N叉树的方式的数量

给定一个n叉树，我们的任务是找到遍历这棵树的总方式数，例如 −

对于上面的树，我们的输出将是192。

对于这个问题，我们需要一些组合学的知识。现在在这个问题中，我们只需要检查每条路径的所有可能组合，这将给我们答案。

找到解决方案的方法

在这个方法中，我们只需要执行一次层次遍历，检查每个节点有多少个子节点，然后将其阶乘乘以答案。

立即学习“C++免费学习笔记（深入）”；

CodeBuddy

腾讯云AI代码助手

下载

示例

上述方法的C++代码

#include
using namespace std;
struct Node{ // structure of our node
    char key;
    vector 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 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和其他语言）编写相同的程序。希望你觉得这个教程有帮助。