Le nombre d'arbres binaires complets où chaque nœud est le produit de ses enfants

Un arbre binaire complet est un type spécial d'arbre binaire dans lequel tous les nœuds parents ont soit deux nœuds enfants, soit aucun nœud enfant. Dans les structures de données, ces types d'arbres sont considérés comme des représentations équilibrées et organisées. Un arbre binaire complet peut avoir la caractéristique unique que chaque nœud parent est le produit de ses nœuds enfants.

Dans cet article, nous aborderons différentes manières de calculer le nombre d'arbres binaires complets en utilisant C++ afin que chaque nœud soit le produit de ses enfants.

Scénarios d'entrée et de sortie

Par exemple, dans le tableau {1, 5, 3, 4}, nous n'avons que quatre nœuds simples 1 (1 x 1), 5 (1 x 5), 3 (1 x 3) et 4 (1 x 4)

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

Dans un tableau donné, en utilisant tous les multiples de chaque élément inférieurs à la valeur maximale, nous pouvons créer un arbre binaire complet si des multiples existent dans le tableau. Par conséquent, nous trouvons la valeur maximale dans le tableau.

Nous commençons par trouver un tel arbre binaire en itérant de la valeur minimale à la valeur maximale, car nous savons que des valeurs plus petites peuvent être des multiples de valeurs plus grandes dans le tableau.

Utilisez la programmation dynamique

Ici, nous utilisons la programmation dynamique pour trouver le nombre d'arbres binaires complets tels que chaque nœud soit le produit de ses enfants. Nous parcourons les éléments du tableau et trouvons des arbres possibles qui satisfont aux conditions ci-dessus. Nous stockons ces solutions dans le vecteur dp .

• Tout d'abord, on trouve les valeurs maximales et minimales dans un tableau en utilisant les constantes INT_MAX et INT_MIN définies dans l'en-tête for.

• Ensuite, nous avons une boucle imbriquée où nous parcourons de la valeur minimale à la valeur maximale du tableau. Dans cette boucle, on vérifie si le vecteur dp est non nul.

• Si le vecteur dp est non nul, alors nous exécutons une autre boucle for pour les multiples de j à partir de (j + j) jusqu'à la valeur maximale. Pour chaque multiple, on vérifie s’il y en a plusieurs.

• S'il y en a plus d'un, alors le nombre d'arbres binaires complets possibles est égal au nombre d'arbres binaires complets de arr[j] et arr[j]/k.

• Nous ajoutons la valeur dp actuellement mise à jour modulo 1000000007 au résultat pour éviter tout débordement de données.

Exemple

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

Sortie

Number of full binary trees satisfying the condition are: 4

Remarque- Ici, la complexité temporelle de ce programme est O(N^2).

Conclusion

Nous avons expliqué comment trouver le nombre d'arbres binaires complets tels que chaque nœud soit le produit de ses propres enfants. Nous résolvons ce problème en utilisant une approche dynamique en stockant la solution du sous-problème dans le vecteur dp. Nous pouvons utiliser une simple boucle for imbriquée pour parcourir de la valeur minimale à la valeur maximale du tableau et vérifier le nombre possible d'arbres binaires complets avec les propriétés souhaitées.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!