Find the number of ways to traverse an N-ary tree using C++-C++-php.cn

Given an N-ary tree, our task is to find the total number of ways to traverse the tree, for example −

Find the number of ways to traverse an N-ary tree using C++

For the above tree, our output will be It's 192.

For this problem, we need some knowledge of combinatorics. Now in this problem we just need to check all possible combinations of each path and this will give us the answer.

Method to find the solution

In this method, we only need to perform a level traversal, check how many children each node has, and then multiply its factorial by the answer.

Example

C code of the above method

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

Copy after login

Output

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

Copy after login

Explanation of the above code

In In this method, we apply BFS (Breadth First Search) or hierarchical traversal and check the number of children of each node. Then, multiply the factorial of that quantity by our answer.

Conclusion

This tutorial introduces several methods of traversing N-ary tree combinations and applies BFS. We also learned a C program and complete method to solve this problem.

We can write the same program in other languages such as C, Java, Python and other languages. Hope you found this tutorial helpful.

The above is the detailed content of Find the number of ways to traverse an N-ary tree using C++. For more information, please follow other related articles on the PHP Chinese website!