数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 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('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 叉树组合学的方法，并通过应用 BFS。我们还学习了这个问题的 C++ 程序以及我们解决的完整方法。
我们可以在其他语言（如 C、Java、Python 等）中编写相同的程序。我们希望您觉得本教程有所帮助。
更新于： 2021-11-25
167 次浏览
广告