একটি বাইনারি গাছের ঘনত্ব তার আকারকে তার উচ্চতা দ্বারা ভাগ করে গণনা করা হয়৷ বাইনারি গাছের ঘনত্ব =আকার/উচ্চতা৷
আসুন প্রথমে স্ট্রাকটটি সংজ্ঞায়িত করি যা একটি ট্রি নোডকে প্রতিনিধিত্ব করবে যেখানে ডেটা এবং এর বাম এবং ডান নোড চাইল্ড রয়েছে। যদি এটি তৈরি করা প্রথম নোড হয় তবে এটি একটি রুট নোড অন্যথায় একটি চাইল্ড নোড।
struct Node {
int data;
struct Node *leftChild, *rightChild;
}; এরপর আমরা আমাদের createNode(int data) ফাংশন তৈরি করি যা একটি int মান নেয় এবং নোডের ডাটা মেম্বারকে বরাদ্দ করি। ফাংশন তৈরি করা স্ট্রাকট নোডে পয়েন্টার ফিরিয়ে দেয়। এছাড়াও, নতুন তৈরি নোডের বাম এবং ডান চাইল্ড নাল সেট করা হয়েছে৷
৷Node* createNode(int data){
Node* node = new Node;
node->data = data;
node->leftChild = node->rightChild = NULL;
return node;
} আমাদের ট্রিডেনসিটি (নোড *রুট) ফাংশন রুট নোড নেয় এবং চেক করে যে এটি নাল কি না। এটি তারপর আকার পরিবর্তনশীল ঘোষণা করে এবং এটি 0 এ সেট করে। heightAndSize(root, size) ফাংশনের রিটার্ন মান উচ্চতা ভেরিয়েবলের জন্য নির্ধারিত হয়। উচ্চতা এবং আকারের মধ্যে সম্পাদিত ফ্লোট বিভাজন তারপর ফেরত দেওয়া হয়।
float treeDensity(Node* root){
if (root == NULL)
return 0;
int size = 0;
int height = heightAndSize(root, size);
return (float)size/height;
} এরপর, heightAndSize(Node* node, int &size) রুট নোড এবং সাইজ ভেরিয়েবলের রেফারেন্স নেয়। রুট নোড শূন্য হলে 0 ফেরত দেওয়া হয়। প্রতিটি সাবট্রির উচ্চতা পুনরাবৃত্তিমূলকভাবে গণনা করা হয় এবং প্রতিটি পুনরাবৃত্তিতে আকার বৃদ্ধি করা হয়। তারপরে আমরা বাম বা ডান সাবট্রির বড়টি ফিরিয়ে দিই।
int heightAndSize(Node* node, int &size){
if (node==NULL)
return 0;
int left = heightAndSize(node->leftChild, size);
int right = heightAndSize(node->rightChild, size);
size++;
return (left > right) ? ++left : ++right;
} উদাহরণ
আসুন আমরা একটি ট্রাভার্সাল −
এ বাইনারি গাছের ঘনত্ব খুঁজে বের করার জন্য নিম্নলিখিত বাস্তবায়নটি দেখি#include<iostream>
using namespace std;
struct Node{
int data;
Node *leftChild, *rightChild;
};
Node* createNode(int data){
Node* node = new Node;
node->data = data;
node->leftChild = node->rightChild = NULL;
return node;
}
int heightAndSize(Node* node, int &size){
if (node==NULL)
return 0;
int left = heightAndSize(node->leftChild, size);
int right = heightAndSize(node->rightChild, size);
size++;
return (left > right) ? ++left : ++right;
}
float treeDensity(Node* root){
if (root == NULL)
return 0;
int size = 0;
int height = heightAndSize(root, size);
return (float)size/height;
}
int main(){
Node* root = createNode(7);
root->leftChild = createNode(9);
root->rightChild = createNode(11);
cout<< "The density of the above given binary tree is "<<treeDensity(root);
return 0;
} আউটপুট
উপরের কোডটি নিম্নলিখিত আউটপুট −
তৈরি করবেThe density of the above given binary tree is 1.5
