给定一棵n元树，计算从根顶点开始遍历n元（或有向无环图）树的方法数。 假设我们有一个给定的N元树，如下所示。
现在我们必须找到从根顶点开始遍历整棵树的方法。有很多这样的方式。下面列出了其中一些。 1) N->M->K->J->B->F->D->E->C->H->I->L->A（一种深度优先遍历）。 2) A->B->F->D->E->K->J->G->C->H->I->N->M->L（级别顺序遍历） 3) ……… 4) ……… . . . 等等…。 我们强烈建议您尽量减少浏览器，并先自己尝试。 遍历所有路径的计数是每个节点的子节点数的阶乘的乘积。请参阅下图以了解清楚-
在这里 “A”有四个孩子，所以有四个！可能的排列 B有两个孩子，所以2个！可能的排列 “F”没有孩子，所以0！可能的排列 ….. 等等 因此，所有这些方法都是-4！*2 ! * 0 ! * 1 ! * 3 ! * 2 ! * 0 ! * 0 ! * 0 ! * 0 ! * 1 ! * 0 ! * 0 ! = 576路 这是一个巨大的方法，其中只有少数几个被证明是有用的，比如-按顺序、按级别顺序、按前顺序、按后顺序（根据这些遍历的流行程度排列）
C++
// C++ program to find the number of ways to traverse a // n-ary tree starting from the root node #include <bits/stdc++.h> using namespace std; // Structure of a node of an n-ary tree struct Node { char key; vector<Node *> child; }; // Utility function to create a new tree node Node *newNode( int key) { Node *temp = new Node; temp->key = key; return temp; } // Untility Function to find factorial of given number int factorial( int n) { if (n == 0) return 1; return n*factorial(n-1); } // Function to calculate the number of ways of traversing // the n-ary starting from root. // This function is just a modified breadth-first search. // We can use a depth-first search too. int calculateWays(Node * root) { int ways = 1; // Initialize result // If the tree is empty there is no way of traversing // the tree. if (root == NULL) return 0; // Create a queue and enqueue root to it. queue<Node *>q; q.push(root); // Level order traversal. while (!q.empty()) { // Dequeue an item from queue and print it Node * p = q.front(); q.pop(); // The number of ways is the product of // factorials of number of children of each node. ways = ways*(factorial(p->child.size())); // Enqueue all childrent of the dequeued item for ( int i=0; i<p->child.size(); i++) q.push(p->child[i]); } return (ways); } // Driver program int main() { /* Let us create below tree * A * / / * B F D E * / | /| * K J G C H I * / * N M L */ Node *root = newNode( 'A' ); (root->child).push_back(newNode( 'B' )); (root->child).push_back(newNode( 'F' )); (root->child).push_back(newNode( 'D' )); (root->child).push_back(newNode( 'E' )); (root->child[0]->child).push_back(newNode( 'K' )); (root->child[0]->child).push_back(newNode( 'J' )); (root->child[2]->child).push_back(newNode( 'G' )); (root->child[3]->child).push_back(newNode( 'C' )); (root->child[3]->child).push_back(newNode( 'H' )); (root->child[3]->child).push_back(newNode( 'I' )); (root->child[0]->child[0]->child).push_back(newNode( 'N' )); (root->child[0]->child[0]->child).push_back(newNode( 'M' )); (root->child[3]->child[2]->child).push_back(newNode( 'L' )); cout << calculateWays(root); ; return 0; } |
Javascript
<script> // JavaScript program to find the // number of ways to traverse a // n-ary tree starting from the root node class Node { constructor(key) { this .child = []; this .key = key; } } // Utility function to create a new tree node function newNode(key) { let temp = new Node(key); return temp; } // Untility Function to find factorial of given number function factorial(n) { if (n == 0) return 1; return n*factorial(n-1); } // Function to calculate the number of ways of traversing // the n-ary starting from root. // This function is just a modified breadth-first search. // We can use a depth-first search too. function calculateWays(root) { let ways = 1; // Initialize result // If the tree is empty there is no way of traversing // the tree. if (root == null ) return 0; // Create a queue and enqueue root to it. let q = []; q.push(root); // Level order traversal. while (q.length > 0) { // Dequeue an item from queue and print it let p = q[0]; q.shift(); // The number of ways is the product of // factorials of number of children of each node. ways = ways*(factorial(p.child.length)); // Enqueue all childrent of the dequeued item for (let i=0; i< p.child.length; i++) q.push(p.child[i]); } return (ways); } /* Let us create below tree * A * / / * B F D E * / | /| * K J G C H I * / * N M L */ let root = newNode( 'A' ); (root.child).push(newNode( 'B' )); (root.child).push(newNode( 'F' )); (root.child).push(newNode( 'D' )); (root.child).push(newNode( 'E' )); (root.child[0].child).push(newNode( 'K' )); (root.child[0].child).push(newNode( 'J' )); (root.child[2].child).push(newNode( 'G' )); (root.child[3].child).push(newNode( 'C' )); (root.child[3].child).push(newNode( 'H' )); (root.child[3].child).push(newNode( 'I' )); (root.child[0].child[0].child).push(newNode( 'N' )); (root.child[0].child[0].child).push(newNode( 'M' )); (root.child[3].child[2].child).push(newNode( 'L' )); document.write(calculateWays(root)); </script> |
输出：
576
时间复杂性： 在水平顺序遍历期间，我们访问每个节点一次，并花费O（n）时间来计算每个节点的阶乘。所花费的总时间为O（Nn），其中N=N元树中的节点数。我们可以通过计算从1到N的所有数字的阶乘来优化解决方案，使其在O（N）时间内工作。 辅助空间： 因为我们只对每个节点使用一个队列和一个结构，所以总体空间复杂度也是O（N）。 常见的陷阱： 因为，阶乘的乘积可能会变得非常巨大，所以它可能会溢出。在C/C++中最好使用-unsigned long long int这样的数据类型，因为方法的数量永远不能是负数。在Java和Python中，有大整数来处理溢出。
本文由 拉希特·贝尔瓦里亚 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以写一篇文章，然后将文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
