Écrit en C++, trouvez le nombre de frères et sœurs d'un nœud donné dans un arbre N-aire

Dans cet article, nous fournirons des informations complètes pour déterminer le nombre de frères et sœurs d'un nœud donné dans un arbre n-aire. Nous devons trouver les nœuds frères de ce nœud en utilisant la valeur clé donnée par l'utilisateur, sinon, sortie -1 ; Il n'y a qu'une seule méthode que nous pouvons utiliser -

Méthode simple

Dans cette méthode, nous allons parcourir tous les nœuds et vérifier si les nœuds enfants ont la même valeur que l'utilisateur. S'il est présent, nous répondons au nombre de nœuds enfants - 1 (la valeur donnée).

Exemple

#include <bits/stdc++.h>
using namespace std;
class Node {  // structure of nodes of our tree.
public:
    int key;
    vector<Node*> child;
    Node(int data){
        key = data;
    }
};
int main(){
   //     Building The Tree
    Node* Base = new Node(50);
    (Base->child).push_back(new Node(2));
    (Base->child).push_back(new Node(30));
    (Base->child).push_back(new Node(14));
    (Base->child).push_back(new Node(60));
    (Base->child[0]->child).push_back(new Node(15));
    (Base->child[0]->child).push_back(new Node(25));
    (Base->child[0]->child[1]->child).push_back(new Node(70));
    (Base->child[0]->child[1]->child).push_back(new Node(100));
    (Base->child[1]->child).push_back(new Node(6));
    (Base->child[1]->child).push_back(new Node(1));
    (Base->child[2]->child).push_back(new Node(7));
    (Base->child[2]->child[0]->child).push_back(new Node(17));
    (Base->child[2]->child[0]->child).push_back(new Node(99));
    (Base->child[2]->child[0]->child).push_back(new Node(27));
    (Base->child[3]->child).push_back(new Node(16));
    int x = 30;
    queue<Node*> q;
    q.push(Base);
    bool flag = 0;
    int answer = -1;
    if(Base -> key != x){
        while(!q.empty()){
            auto parent = q.front();
            q.pop();
            for(int i = 0; i < parent -> child.size(); i++){
                if(parent -> child[i] -> key == x){
                    answer = parent -> child.size() - 1;
                    flag = 1;
                    break;
                }
                q.push(parent -> child[i]);
            }
            if(flag)
                break;
        }
        cout << answer << "\n";
    }
    else
        cout << "0\n";
    return 0;
}

Sortie

3

Description du programme ci-dessus

Dans ce programme, nous maintenons une file d'attente contenant des nœuds non visités et ferons apparaître les nœuds visités. Maintenant, lorsque nous explorons un nœud, nous explorons ses enfants et si la valeur de l'enfant correspond à x alors notre indicateur est déclenché et notre variable de réponse a reçu la valeur child.size() - 1, puis nous sortons de la boucle for. et maintenant nous vérifions si le drapeau est déclenché. S'il se déclenche, nous quittons la boucle while. Après cela, s'il n'y a aucun nœud avec la valeur donnée, nous imprimons maintenant la réponse, donc notre variable de réponse ne change pas et la sortie sera -1. Si la valeur racine est la même que la valeur donnée, il existe une instruction if qui vérifie la valeur et exécute notre programme.

Conclusion

Dans cet article, nous avons résolu un problème pour trouver le nombre de frères et sœurs d'un nœud donné dans un arbre n-aire de complexité temporelle O(N). Nous avons également appris un programme C++ pour résoudre ce problème et une méthode complète pour résoudre ce problème. Nous pouvons écrire le même programme dans d’autres langages, tels que C, Java, Python et d’autres langages.

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!