Trouver le nombre de façons de parcourir un arbre N-aire en utilisant C++

Étant donné un arbre N-aire, notre tâche est de trouver le nombre total de façons de parcourir l'arbre, par exemple −

Pour l'arbre ci-dessus, notre résultat sera de 192.

Pour ce problème, nous avons besoin de quelques connaissances en combinatoire. Maintenant, dans ce problème, il nous suffit de vérifier toutes les combinaisons possibles de chaque chemin et cela nous donnera la réponse.

Méthode pour trouver la solution

Dans cette méthode, il nous suffit d'effectuer un parcours de niveau, de vérifier combien d'enfants a chaque nœud, puis de le multiplier factoriellement par la réponse.

Exemple

Code C++ de la méthode ci-dessus

#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

Explication du code ci-dessus

Dans cette méthode, nous appliquons BFS (Breadth First Search) ou parcours hiérarchique et vérifions les enfants de chaque nœud Nombre de nœuds. Ensuite, multipliez la factorielle de cette quantité par notre réponse.

Conclusion

Ce tutoriel a présenté plusieurs méthodes de parcours de combinaisons d'arbres N-aires et appliqué BFS. Nous avons également appris le programme C++ et la méthode complète pour résoudre ce problème.

Nous pouvons écrire le même programme dans d'autres langages comme C, Java, Python et d'autres langages. J'espère que vous avez trouvé ce tutoriel utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!