Bilangan pokok binari penuh di mana setiap nod adalah hasil darab anak-anaknya

Pokok binari penuh ialah jenis pokok binari khas di mana semua nod induk sama ada mempunyai dua nod anak atau tiada nod anak. Dalam struktur data, jenis pokok ini dianggap sebagai perwakilan yang seimbang dan teratur. Pokok binari yang lengkap mungkin mempunyai ciri unik bahawa setiap nod induk adalah hasil daripada anak-anaknya.

Dalam artikel ini, kita akan membincangkan cara berbeza untuk mengira bilangan pokok binari lengkap menggunakan C++ supaya setiap nod adalah hasil daripada anak-anaknya.

Senario input dan output

Sebagai contoh, dalam tatasusunan {1, 5, 3, 4}, kita hanya mempunyai empat nod tunggal 1 (1 x 1), 5 (1 x 5), 3 (1 x 3) dan 4 (1 x 4)

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

Dalam tatasusunan yang diberikan, menggunakan semua gandaan setiap elemen kurang daripada nilai maksimum, kita boleh mencipta pepohon binari lengkap jika gandaan wujud dalam tatasusunan. Oleh itu, kita dapati nilai maksimum dalam tatasusunan.

Kita mulakan dengan mencari pokok binari sedemikian dengan mengulangi daripada nilai minimum kepada nilai maksimum, kerana kita tahu bahawa nilai yang lebih kecil mungkin merupakan gandaan nilai yang lebih besar dalam tatasusunan.

Gunakan pengaturcaraan dinamik

Di sini, kami menggunakan pengaturcaraan dinamik untuk mencari bilangan pokok binari penuh supaya setiap nod adalah hasil daripada anak-anaknya. Kami mengulangi elemen tatasusunan dan mencari kemungkinan pokok yang memenuhi syarat di atas. Kami menyimpan penyelesaian ini dalam vektor dp .

• Pertama, kami mencari nilai maksimum dan minimum dalam tatasusunan menggunakan pemalar INT_MAX dan INT_MIN ditakrifkan dalam pengepala untuk.

• Seterusnya, kami mempunyai gelung bersarang di mana kami mengulangi daripada nilai minimum kepada nilai maksimum tatasusunan. Dalam gelung ini, kami menyemak sama ada vektor dp bukan sifar.

• Jika vektor dp bukan sifar, maka kita jalankan satu lagi gelung untuk gandaan j bermula dari (j + j) sehingga nilai maksimum. Untuk setiap gandaan, kami menyemak sama ada terdapat lebih daripada satu.

• Jika terdapat lebih daripada satu, maka bilangan pokok binari penuh yang mungkin adalah sama dengan bilangan pokok binari penuh arr[j] dan arr[j]/k.

• Kami menambah modulo nilai dp yang kini dikemas kini 1000000007 kepada hasil untuk mengelakkan limpahan data.

Contoh

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

Output

Number of full binary trees satisfying the condition are: 4

Nota- Di sini, kerumitan masa program ini ialah O(N^2).

Kesimpulan

Kami telah membincangkan cara mencari bilangan pokok binari penuh supaya setiap nod adalah hasil daripada anak-anaknya sendiri. Kami menyelesaikan masalah ini menggunakan pendekatan dinamik dengan menyimpan penyelesaian kepada submasalah dalam vektor dp. Kita boleh menggunakan gelung bersarang untuk mudah untuk beralih daripada nilai minimum kepada nilai maksimum tatasusunan dan semak kemungkinan bilangan pokok binari lengkap dengan sifat yang dikehendaki.

Atas ialah kandungan terperinci Bilangan pokok binari penuh di mana setiap nod adalah hasil darab anak-anaknya. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!