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 < in C++ definiert sind. Aktualisieren Sie die Maximal- und Minimalwerte, indem Sie die 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.

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

Number of full binary trees satisfying the condition are: 4