সি++-এ এক ট্রাভার্সালে বাইনারি ট্রির ঘনত্ব

একটি বাইনারি ট্রির ঘনত্ব (density) এর আকার (size) কে এর উঁচুতা (height) দিয়ে ভাগ করে বের করা হয়। বাইনারি ট্রি ডেন্সিটি = size/height।

প্রথমে স্ট্রাক্ট ডিফাইন করি যা ট্রি নোড রিপ্রেজেন্ট করবে যাতে ডেটা এবং এর বাম ও ডান চাইল্ড নোড থাকে। যদি এটি প্রথম নোড হয় তবে এটি রুট নোড হবে অন্যথায় চাইল্ড নোড।

struct Node { 
    int data; 
    struct Node *leftChild, *rightChild; 
};

পরবর্তীতে createNode(int data) ফাংশন তৈরি করি যা একটি int মান নেয় এবং সেটি নোডের ডেটা মেম্বরে অ্যাসাইন করে। ফাংশনটি তৈরি হওয়া struct Node-এর পয়েন্টার ফেরত দেয়। এছাড়া নতুন নোডের বাম ও ডান চাইল্ড নাল সেট করা হয়।

Node* createNode(int data){ 
    Node* node = new Node; 
    node->data = data; 
    node->leftChild = node->rightChild = NULL; 
    return node; 
}

আমাদের treeDensity(Node *root) ফাংশন রুট নোড নেয় এবং চেক করে এটি নাল কিনা। তারপর size ভেরিয়েবল ডিক্লেয়ার করে ০ সেট করা হয়। heightAndSize(root, size) ফাংশন থেকে ফেরত আসা মান height ভেরিয়েবলে অ্যাসাইন করা হয়। height এবং size-এর মধ্যে float ডিভিশন পারফর্ম করে ফেরত দেওয়া হয়।

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) রুট নোড এবং size ভেরিয়েবলের রেফারেন্স নেয়। যদি রুট নোড NULL হয় তবে ০ ফেরত দেয়। প্রতিটি সাবট্রির হাইট রিকার্সিভলি ক্যালকুলেট করা হয় এবং প্রতিটি রিকার্শনে size বাড়ানো হয়। তারপর বাম বা ডান সাবট্রির বড়টি ফেরত দেয়।

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