使用 C++ 遍历 N 叉树的路径数

给定一个 N 叉树，我们的任务是找到遍历这棵树的总路径数，例如：

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

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

解决方案方法

在这种方法中，我们只需要执行层序遍历并检查每个节点有多少个子节点，然后简单地将它的阶乘乘以答案。

示例

上述方法的 C++ 代码

Open Compiler
#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;
}

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输出

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

上述代码的解释

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

结论

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

我们可以在其他语言（如 C、Java、Python 等）中编写相同的程序。我们希望您觉得本教程有所帮助。

更新于： 2021-11-25

167 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告