এই টিউটোরিয়ালে, আমরা শিখতে যাচ্ছি কিভাবে একটি একক ট্রাভার্সালে বাইনারি গাছের ঘনত্ব খুঁজে বের করতে হয়।
গাছের উচ্চতা দ্বারা গাছের আকারকে ভাগ করে বাইনারি গাছের ঘনত্ব পাওয়া যায়।
বাইনারি গাছের আকার হল প্রদত্ত বাইনারি ট্রিতে উপস্থিত মোট নোডের সংখ্যা।
বাইনারি গাছের উচ্চতা হল রুট নোড থেকে পাতার নোডের সর্বোচ্চ গভীরতা।
আসুন সমস্যা সমাধানের পদক্ষেপগুলি দেখি৷
৷-
বাইনারি ট্রি ডামি ডেটা শুরু করুন।
-
গাছের আকার এবং উচ্চতা খুঁজুন।
-
পুনরাবৃত্তভাবে গাছের উচ্চতা গণনা করুন।
-
বাম নোড ট্রি উচ্চতা ফেরত দিন যদি এটি ডান নোড গাছের উচ্চতার চেয়ে বেশি হয় অন্যথায় উভয় 1 যোগ করে ডান নোড গাছের উচ্চতা ফেরত দিন।
-
নোডের আকার বৃদ্ধি করুন।
-
-
$$size\:of\:Tree\:/\:height\:of\:Tree$$।
সূত্র ব্যবহার করে গাছের ঘনত্ব গণনা করুন। -
গাছের ঘনত্ব প্রিন্ট করুন।
উদাহরণ
আসুন কোডটি দেখি।
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right;
};
Node* newNode(int data) {
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
int findHeightAndSizeOfTree(Node* node, int &size) {
if (node == NULL) {
return 0;
}
int leftTreeCount = findHeightAndSizeOfTree(node->left, size);
int rightTreeCount = findHeightAndSizeOfTree(node->right, size);
size++;
return (leftTreeCount > rightTreeCount) ? leftTreeCount + 1 : rightTreeCount + 1;
}
float treeDensity(Node* root) {
if (root == NULL) {
return 0;
}
int treeSize = 0;
int treeHeight = findHeightAndSizeOfTree(root, treeSize);
return (float)treeSize/treeHeight;
}
int main() {
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
cout << treeDensity(root) << endl;
return 0;
} আউটপুট
আপনি যদি উপরের প্রোগ্রামটি চালান, তাহলে আপনি নিম্নলিখিত ফলাফল পাবেন।
2.33333
উপসংহার
টিউটোরিয়ালে আপনার কোন প্রশ্ন থাকলে মন্তব্য বিভাগে উল্লেখ করুন।
