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

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

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<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(&#39;A&#39;);
    (root->child).push_back(createNode(&#39;B&#39;));
    (root->child).push_back(createNode(&#39;F&#39;));
    (root->child).push_back(createNode(&#39;D&#39;));
    (root->child).push_back(createNode(&#39;E&#39;));
    (root->child[2]->child).push_back(createNode(&#39;K&#39;));
    (root->child[1]->child).push_back(createNode(&#39;J&#39;));
    (root->child[3]->child).push_back(createNode(&#39;G&#39;));
    (root->child[0]->child).push_back(createNode(&#39;C&#39;));
    (root->child[2]->child).push_back(createNode(&#39;H&#39;));
    (root->child[1]->child).push_back(createNode(&#39;I&#39;));
    (root->child[2]->child[0]->child).push_back(createNode(&#39;N&#39;));
    (root->child[2]->child[0]->child).push_back(createNode(&#39;M&#39;));
    (root->child[1]->child[1]->child).push_back(createNode(&#39;L&#39;));
    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;
}

Output

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

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!