এই টিউটোরিয়ালে আমরা শিখব কিভাবে একক ট্রাভার্সালে বাইনারি ট্রির ঘনত্ব বের করা যায়।
বাইনারি ট্রির ঘনত্ব পাওয়া যায় ট্রির সাইজকে ট্রির হাইট দিয়ে ভাগ করে।
বাইনারি ট্রির সাইজ হলো দেয়া বাইনারি ট্রিতে মোট নোডের সংখ্যা।
বাইনারি ট্রির হাইট হলো রুট নোড থেকে লিফ নোডের সর্বোচ্চ গভীরতা।
সমস্যা সমাধানের ধাপগুলো:
ডামি ডেটা দিয়ে বাইনারি ট্রি ইনিশিয়ালাইজ করুন।
ট্রির সাইজ এবং হাইট বের করুন।
রিকারসিভভাবে ট্রির হাইট গণনা করুন।
লেফট সাবট্রির হাইট যদি রাইট সাবট্রির হাইটের চেয়ে বড় হয় তবে লেফট সাবট্রির হাইট রিটার্ন করুন অন্যথায় রাইট সাবট্রির হাইট রিটার্ন করুন, উভয় কেসে ১ যোগ করে।
নোডের সাইজ বাড়ান।
ফর্মুলা $$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
উপসংহার
টিউটোরিয়াল সম্পর্কে কোনো প্রশ্ন থাকলে কমেন্ট সেকশনে জানান।
