Anzahl der Pfade von der Wurzel zu den Blättern mit höchstens M aufeinanderfolgenden Knoten und dem Wert K

Einführung

Binärbaum ist eine faszinierende Datenstruktur mit einem breiten Anwendungsspektrum in der Informatik und Programmierung. Ein interessantes Problem besteht darin, die Anzahl eines gegebenen Baums zu ermitteln, der aus einem übergeordneten Knoten und seinen untergeordneten Knoten besteht. Ein Binärbaum besteht aus Knoten, der Wurzelknoten wird bestimmt und der Wurzelknoten kann entsprechend den Benutzeranforderungen untergeordnete Knoten bereitstellen. Der K-Wert wird bestimmt und die Bewegungsmethode wird durch den M-Wert ausgewählt.

Anzahl der Wurzel-zu-Blatt-Pfade

Das Diagramm wird mithilfe verschiedener Knoten erstellt, die Werte in Form von Ganzzahlen enthalten. Dieser Artikel konzentriert sich hauptsächlich auf das Zählen vom Startknoten oder Wurzelknoten bis zum Blattknoten oder untergeordneten Knoten.

Beispiel

Der Graph wird aus einem Binärbaum mit verschiedenen Knoten erstellt.

• Im obigen Binärbaum wird der Wurzelknoten als „8“ ausgewählt.

• Dann erstellen Sie zwei Knoten, einen mit dem Wert 3 und den anderen mit dem Wert 10, die die linke und rechte Position des Wurzelknotens einnehmen.

• Nehmen Sie den Knoten mit dem Wert 2 als Wurzel und erstellen Sie einen weiteren untergeordneten Knoten mit den Werten 2 und 1 als linken bzw. rechten Knoten.

• Schließlich erstellt der untergeordnete Knoten mit dem Wert 1 einen untergeordneten Knoten mit dem Wert -4.

Methode 1: C++-Code zur Berechnung eines Wurzel-zu-Blatt-Pfads, der aus bis zu M aufeinanderfolgenden Knoten mit K Werten besteht, mithilfe einer rekursiven Funktion

Um dieses Problem effizient zu lösen, verwenden wir grundlegende Konzepte wie den Baumdurchquerungsalgorithmus und die Rekursion.

Algorithmus

Schritt 1: Erstellen Sie eine Struktur zur Darstellung des Baumknotens, die zwei Zeiger (linker untergeordneter Knoten und rechter untergeordneter Knoten) und ein Ganzzahlfeld zum Speichern des Knotenwerts enthält.

Schritt 2: Entwerfen Sie eine rekursive Funktion, um den Binärbaum ausgehend von der Wurzel zu durchlaufen und dabei die aktuelle Pfadlänge (initialisiert auf 0), die Anzahl aufeinanderfolgender Vorkommen (ursprünglich auf 0 gesetzt), den Zielwert K usw. zu verfolgen die maximal zulässige Anzahl aufeinanderfolgender Vorkommen M .

Schritt 3: Rufen Sie die Funktion rekursiv für jeden linken und rechten Teilbaum auf und übergeben Sie dabei aktualisierte Parameter wie die inkrementelle Pfadlänge und die Anzahl aufeinanderfolgender Vorkommen (falls zutreffend).

Schritt 4: Für jeden nicht leeren Knoten, der während der Durchquerung besucht wird:

a) Wenn sein Wert gleich K ist, addieren Sie eins zu beiden Variablen.

b) Setzen Sie die Variable auf Null zurück, wenn ihr Wert nicht mit K übereinstimmt oder die Anzahl der aufeinanderfolgenden Vorkommen von M überschreitet, die bisher im Pfad aufgetreten sind.

Schritt 5: Wenn der untergeordnete Knoten beim Durchlaufen des Baums sowohl im linken als auch im rechten Fall einen Wert von Null hat, können wir auf zwei Arten damit umgehen, d. h.

a) Überprüfen Sie, ob die Variable M nicht überschreitet.

b) Wenn ja, erhöhen Sie die Gesamtzahl der Pfade, die die Bedingung erfüllen, um 1.

Beispiel

//including the all in one header
#include<bits/stdc++.h>
using namespace std;
//creating structure with two pointers as up and down
struct Vertex {
   int data;
   struct Vertex* up;
   struct Vertex* down;
};
//countPaths function declared with five arguments ; with root = end; Node= vertex; left = up; right = down
int countPaths(Vertex* end, int K, int M, int currCount, int 
consCount) {
//To check the condition when the root is equal to 1 and greater than the maximum value, the values is incremented
   if (end == NULL || consCount > M) {
      return 0;
   }
//To check when the root is equal to the K value, increment by 1
   if (end->data == K) {
      currCount++;
      consCount++;
   } else {
//If it is not equal, it will return 0
      currCount = 0;
   }
   if (end->up == NULL && end->down == NULL) {
      if (currCount <= M) {
         return 1;
      } else {
         return 0;
      }
   }
   return countPaths(end->up, K, M, currCount, consCount) + countPaths(end->down, K, M, currCount, consCount);
}
//Main function to test the implementation
int main() {
   Vertex* end = new Vertex();
   end->data = 8;
   end->up = new Vertex();
   end->up->data = 3;
   end->down = new Vertex();
   end->down->data = 10;
   end->up->up = new Vertex();
   end->up->up->data = 2;
   end->up->down = new Vertex();
   end->up->down->data = 1;
   end->up->down->up = new Vertex();
   end->up->down->up->data = -4;

   int K = 1; // Value of node
   int M = 2; // Maximum consecutive nodes
   int currCount = -1; // Current count
   int consCount = -1; // Consecutive count

   cout << "The number of paths obtained from the given graph of" << M << "nodes with a value of " << K << " is " << countPaths(end, K, M, currCount, consCount) << endl;

   return 0;
} 

Ausgabe

The number of paths obtained from the given graph of 2 nodes with a value of 1 is 3

Fazit

In diesem Artikel untersuchen wir das Problem der Zählung der Anzahl der Pfade von der Spitze (d. h. dem Blatt) bis zur Spitze oder Wurzel. Solche Probleme können durch den Einsatz von Baumdurchlaufalgorithmen und rekursiven Techniken in C++ effizient gelöst werden. Das Durchlaufen eines Binärbaums mag schwierig erscheinen, anhand von Beispielen wird es jedoch einfacher.

Das obige ist der detaillierte Inhalt vonAnzahl der Pfade von der Wurzel zu den Blättern mit höchstens M aufeinanderfolgenden Knoten und dem Wert K. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!