समस्या कथन
एक बाइनरी ट्री को देखते हुए, दिए गए ट्री की अधिकतम चौड़ाई प्राप्त करने के लिए एक फ़ंक्शन लिखें। एक पेड़ की चौड़ाई सभी स्तरों की अधिकतम चौड़ाई होती है।
पेड़ के नीचे विचार करें -
10 / \ 7 4 / \ \ 9 2 1 / \ 2 5 1. Width at level 1: 1 2. Width at level 2: 2 3. Width at level 3: 3 4. Width at level 4: 2 For above tree answer is 3.
एल्गोरिदम
1. Use level order traversal to find the answer
उदाहरण
#include <bits/stdc++.h>
using namespace std;
struct node {
public:
int data;
node* left;
node* right;
};
int getWidth(node* root, int level);
int height(node* node);
node* newNode(int data);
int getMaxWidth(node* root){
int maxWidth = 0;
int width;
int h = height(root);
int i;
for (i = 1; i <= h; ++i) {
width = getWidth(root, i);
if (width > maxWidth) {
maxWidth = width;
}
}
return maxWidth;
}
int getWidth(node* root, int level){
if (root == NULL) {
return 0;
}
if (level == 1) {
return 1;
}
else if (level > 1) {
return getWidth(root->left, level - 1) + getWidth(root->right, level - 1);
}
}
int height(node* node){
if (node == NULL) {
return 0;
}
int lHeight = height(node->left);
int rHeight = height(node->right);
return (lHeight > rHeight)? (lHeight + 1): (rHeight + 1);
}
node* newNode(int data){
node* Node = new node();
Node->data = data;
Node->left = NULL;
Node->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<<"Maximum width = " << getMaxWidth(root) << endl;
return 0;
} आउटपुट
जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्न आउटपुट उत्पन्न करता है -
Maximum width = 3