Ermitteln Sie in C++ die Anzahl der Geschwister eines bestimmten Knotens in einem N-fachen Baum

In diesem Artikel stellen wir vollständige Informationen zur Verfügung, um die Anzahl der Geschwister eines bestimmten Knotens in einem n-fachen Baum zu bestimmen. Wir müssen die Geschwisterknoten dieses Knotens mithilfe des vom Benutzer angegebenen Schlüsselwerts finden. Wenn nicht, geben Sie -1 aus. Es gibt nur eine Methode, die wir verwenden können –

Einfache Methode

Bei dieser Methode durchlaufen wir alle Knoten und prüfen, ob die untergeordneten Knoten denselben Wert wie der Benutzer haben. Falls vorhanden, antworten wir mit der Anzahl der untergeordneten Knoten - 1 (der angegebene Wert).

Beispiel

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

Ausgabe

3

Beschreibung des obigen Programms

In diesem Programm verwalten wir eine Warteschlange mit nicht besuchten Knoten und löschen die besuchten Knoten. Wenn wir nun einen Knoten erkunden, erkunden wir seine untergeordneten Knoten. Wenn der Wert des untergeordneten Knotens mit x übereinstimmt, wird unser Flag ausgelöst und unserer Antwortvariablen wurde der Wert child.size() - 1 zugewiesen. Dann verlassen wir die for-Schleife und jetzt prüfen wir, ob das Flag ausgelöst wird. Wenn es ausgelöst wird, verlassen wir die while-Schleife. Wenn danach kein Knoten mit dem angegebenen Wert vorhanden ist, drucken wir nun die Antwort aus, sodass sich unsere Antwortvariable nicht ändert und die Ausgabe -1 ist. Wenn der Stammwert mit dem angegebenen Wert übereinstimmt, gibt es eine if-Anweisung, die den Wert prüft und unser Programm ausführt.

Fazit

In diesem Artikel haben wir ein Problem gelöst, um die Anzahl der Geschwister eines bestimmten Knotens in einem n-fachen Baum mit der Zeitkomplexität O(N) zu ermitteln. Wir haben auch ein C++-Programm zur Lösung dieses Problems und eine vollständige Methode zur Lösung dieses Problems gelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen Sprachen schreiben.

Das obige ist der detaillierte Inhalt vonErmitteln Sie in C++ die Anzahl der Geschwister eines bestimmten Knotens in einem N-fachen Baum. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!