C++ এ একটি বাইনারি গাছের সর্বোচ্চ প্রস্থ

সমস্যা বিবৃতি

একটি বাইনারি ট্রি দেওয়া হয়েছে, প্রদত্ত গাছের সর্বাধিক প্রস্থ পেতে একটি ফাংশন লিখুন। একটি গাছের প্রস্থ হল সব স্তরের প্রস্থের সর্বোচ্চ।

নীচের গাছটি বিবেচনা করুন -

 10 / \ 7 4 / \ \ 9 2 1 / \ 2 51. লেভেল 1-এ প্রস্থ:12। লেভেল 2-এ প্রস্থ:23। লেভেল 3-এ প্রস্থ:34। লেভেল 4-এ প্রস্থ:2 উপরের গাছের উত্তর হল 3.

অ্যালগরিদম

উদাহরণ

#include নেমস্পেস ব্যবহার করে std;struct node { public:int data; নোড* বাম; node* right;};int getWidth(node* root, int level);int height(node* node);node* newNode(int data);int getMaxWidth(node* root){int maxWidth =0; int প্রস্থ; int h =উচ্চতা(মূল); int i; জন্য (i =1; i <=h; ++i) { প্রস্থ =getWidth(root, i); যদি (প্রস্থ> maxWidth) { maxWidth =width; } } রিটার্ন maxWidth;}int getWidth(node* root, int level){ if (root ==NULL) { return 0; } যদি (লেভেল ==1) { রিটার্ন 1; } অন্যথায় যদি (লেভেল> 1) { ফেরত getWidth(root->left, level - 1) + getWidth(root->ডান, লেভেল - 1); }} int উচ্চতা(নোড* নোড){ if (নোড ==NULL) { রিটার্ন 0; } int lHeight =height(node->left); int rHeight =উচ্চতা(নোড->ডান); রিটার্ন (lHeight> rHeight)? (lHeight + 1):(rHeight + 1);}নোড* newNode(int data){ node* Node =new node(); নোড->ডেটা =ডেটা; নোড->বাম =NULL; নোড->right =NULL; return(Node);}int main(){ node *root =newNode(10); root->left =newNode(7); root->right =newNode(4); root->left->left =newNode(9); root->left->right =newNode(2); root->right->right =newNode(1); root->right->right->left =newNode(2); root->right->right->right =newNode(5); cout<<"সর্বোচ্চ প্রস্থ =" < 
আউটপুট
 
যখন আপনি উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করেন। এটি নিম্নলিখিত আউটপুট −
 তৈরি করে 
সর্বোচ্চ প্রস্থ =3