Tiefensuche von Teilbäumen in einem Baum mit C++

In diesem Problem erhalten wir einen Binärbaum und müssen DFS von einem bestimmten Knoten aus ausführen, wobei wir den angegebenen Knoten als Root annehmen und DFS von dort aus ausführen.

Nehmen wir im obigen Baum an, dass wir den DFS-Knoten F ausführen müssen.

In diesem Tutorial werden wir einige unorthodoxe Methoden anwenden, um unsere Zeitkomplexität erheblich zu reduzieren, sodass wir diesen Code auch unter Einschränkungen ausführen können.

Methode – Bei diesem Ansatz wählen wir nicht den naiven Ansatz, d. h. wir wenden einfach dfs auf jeden Knoten an, da dies bei höheren Einschränkungen nicht funktioniert. Deshalb versuchen wir, etwas Unorthodoxes zu verwenden, um den Erhalt eines TLE zu vermeiden.

#include <bits/stdc++.h>
using namespace std;
#define N 100000
// Adjacency list to store the
// tree nodes connections
vector<int> v[N];
unordered_map<int, int> mape; // will be used for associating the node with it&#39;s index
vector<int> a;
void dfs(int nodesunder[], int child, int parent){ // function for dfs and     precalculation our nodesunder
    a.push_back(child); // storing the dfs of our tree
    // nodesunder of child subtree
    nodesunder[child] = 1;
    for (auto it : v[child]) { // performing normal dfs

        if (it != parent) { // as we the child can climb up to
        //it&#39;s parent so we are trying to avoid that as it will become a cycle
            dfs(nodesunder, it, child); // recursive call
            nodesunder[child] += nodesunder[it]; // storing incrementing the nodesunder
        //by the number of nodes under it&#39;s children
        }
    }
}
// Function to print the DFS of subtree of node
void printDFS(int node, int nodesunder[]){
    int ind = mape[node]; // index of our node in the dfs array
    cout << "The DFS of subtree " << node << ": ";
    // print the DFS of subtree
    for (int i = ind; i < ind + nodesunder[node]; i++){ // going through dfs array and then
    //printing all the nodes under our given node
        cout << a[i] << " ";
    }
    cout << endl;
}
void addEdgetoGraph(int x, int y){ // for maintaining adjacency list
    v[x].push_back(y);
    v[y].push_back(x);
}
void mark(){ // marking each node with it&#39;s index in dfs array
    int size = a.size();
    // marks the index
    for (int i = 0; i < size; i++) {
       mape[a[i]] = i;
    }
}
int main(){
    int n = 7;
    // add edges of a tree
    addEdgetoGraph(1, 2);
    addEdgetoGraph(1, 3);
    addEdgetoGraph(2, 4);
    addEdgetoGraph(2, 5);
    addEdgetoGraph(4, 6);
    addEdgetoGraph(4, 7);
    // array to store the nodes present under of subtree
    // of every node in a tree
    int nodesunder[n + 1];
    dfs(nodesunder, 1, 0); // generating our nodesunder array
    mark(); // marking the indices in map
    // Query 1
    printDFS(2, nodesunder);
    // Query 2
    printDFS(4, nodesunder);
    return 0;
}

Ausgabe

The DFS of subtree 2: 2 4 6 7 5
The DFS of subtree 4: 4 6 7

Verstehen Sie den Code

Bei dieser Methode berechnen wir die Reihenfolge von dfs vorab und speichern sie im Vektor. Wenn wir dfs vorab berechnen, berechnen wir auch jeden Teilbaum, beginnend mit jedem Knoten, der unter then existiert, und dann einfach Gehen Sie vom Startindex des Knotens zur Anzahl aller Knoten, die in seinem Unterbaum vorhanden sind.

Fazit

In diesem Tutorial haben wir ein Problem gelöst, um die folgende Abfrage zu lösen: DFS von Teilbäumen in einem Baum. Wir haben auch ein C++-Programm für dieses Problem und eine vollständige Methode zur Lösung dieses Problems (Normal) gelernt.

Wir können das gleiche Programm in anderen Sprachen schreiben (wie C, Java, Python usw.). Ich hoffe, dieser Artikel ist hilfreich für Sie.

Das obige ist der detaillierte Inhalt vonTiefensuche von Teilbäumen in einem Baum mit C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!