Die Anzahl vollständiger Binärbäume, bei denen jeder Knoten das Produkt seiner untergeordneten Knoten ist

Ein vollständiger Binärbaum ist eine spezielle Art von Binärbaum, bei dem alle übergeordneten Knoten entweder zwei untergeordnete Knoten oder keine untergeordneten Knoten haben. In Datenstrukturen gelten diese Baumtypen als ausgewogene und organisierte Darstellungen. Ein vollständiger Binärbaum kann die einzigartige Eigenschaft haben, dass jeder übergeordnete Knoten das Produkt seiner untergeordneten Knoten ist.

In diesem Artikel besprechen wir verschiedene Methoden zur Berechnung der Anzahl vollständiger Binärbäume mit C++, sodass jeder Knoten das Produkt seiner untergeordneten Knoten ist.

Eingabe- und Ausgabeszenarien

Zum Beispiel haben wir im Array {1, 5, 3, 4} nur vier einzelne Knoten 1 (1 x 1), 5 (1 x 5), 3 (1 x 3) und 4 (1 x 4). .

Input: arr = {1, 5, 3, 4}
Output: 4

In einem bestimmten Array können wir unter Verwendung aller Vielfachen jedes Elements, die kleiner als der Maximalwert sind, einen vollständigen Binärbaum erstellen, wenn im Array Vielfache vorhanden sind. Daher finden wir den Maximalwert im Array.

Wir beginnen damit, einen solchen Binärbaum zu finden, indem wir vom Minimalwert zum Maximalwert iterieren, da wir wissen, dass kleinere Werte ein Vielfaches größerer Werte im Array sein können.

Verwenden Sie dynamische Programmierung

Hier verwenden wir dynamische Programmierung, um die Anzahl vollständiger Binärbäume zu ermitteln, sodass jeder Knoten das Produkt seiner untergeordneten Knoten ist. Wir iterieren über die Array-Elemente und finden mögliche Bäume, die die oben genannten Bedingungen erfüllen. Wir speichern diese Lösungen im dp -Vektor.

• Zuerst finden wir die Maximal- und Minimalwerte in einem Array mithilfe der Konstanten INT_MAX und INT_MIN, die im Header for-Schleife wiederholen.

• Als nächstes haben wir eine verschachtelte Schleife, in der wir vom Minimalwert zum Maximalwert des Arrays iterieren. In dieser Schleife prüfen wir, ob der dp-Vektor ungleich Null ist.

• Wenn der dp-Vektor ungleich Null ist, führen wir eine weitere for-Schleife für Vielfache von j aus, beginnend mit (j + j) bis zum Maximalwert. Für jedes Vielfache prüfen wir, ob es mehr als eins gibt.

• Wenn es mehr als einen gibt, dann ist die Anzahl der möglichen vollständigen Binärbäume gleich der Anzahl der vollständigen Binärbäume von arr[j] und arr[j]/k.

• Wir addieren den aktuell aktualisierten dp-Wert Modulo 1000000007 zum Ergebnis, um einen Datenüberlauf zu verhindern.

Beispiel

#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>

using namespace std;

int numOfFullBinaryTrees(int arr[], int N) {
   int minValue = INT_MAX;
   int maxValue = INT_MIN;

   // Find the maximum and minimum value from the array
   for (int j = 0; j < N; j++) {
      minValue = min(minValue, arr[j]);
      maxValue = max(maxValue, arr[j]);
   }

   vector < int > dp(maxValue + 1, 0);

   // One possible full binary tree for each element 
   // in case of single nodes
   for (int j = 0; j < N; j++) {
      dp[arr[j]] = 1;
   }

   int result = 0;
   for (int j = minValue; j <= maxValue; j++) {
      if (dp[j] != 0) {
         for (int k = j + j; k <= maxValue && (k / j) <= j; k += j) {
            if (dp[k] != 0) {
               dp[k] += (dp[j] * dp[k / j]);
               // Check if left child may become right child and vice versa
               if (j != (k / j)) {
                  dp[k] += (dp[j] * dp[k / j]);
               }
            }
         }
         result = (result + dp[j]) % 1000000007;
      }
   }
   return result;
}

int main() {
   int array[] = {12, 3, 5, 6};
   int N = sizeof(array) / sizeof(array[0]);
   cout << "Number of full binary trees satisfying the condition are: " << numOfFullBinaryTrees(array, N) << endl;
   return 0;
}

Ausgabe

Number of full binary trees satisfying the condition are: 4

Hinweis – Hier beträgt die zeitliche Komplexität dieses Programms O(N^2).

Fazit

Wir haben besprochen, wie man die Anzahl vollständiger Binärbäume ermittelt, sodass jeder Knoten das Produkt seiner eigenen untergeordneten Knoten ist. Wir lösen dieses Problem mithilfe eines dynamischen Ansatzes, indem wir die Lösung des Teilproblems im dp-Vektor speichern. Wir können eine einfache verschachtelte for-Schleife verwenden, um vom minimalen zum maximalen Wert des Arrays zu iterieren und die mögliche Anzahl vollständiger Binärbäume mit den gewünschten Eigenschaften zu überprüfen.

Das obige ist der detaillierte Inhalt vonDie Anzahl vollständiger Binärbäume, bei denen jeder Knoten das Produkt seiner untergeordneten Knoten ist. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!