इस समस्या में, हमें एक बाइनरी ट्री दिया जाता है और हमें बाइनरी ट्री के सभी लीफ नोड्स को दाएं से बाएं प्रिंट करना होता है।
आइए समस्या को समझने के लिए एक उदाहरण लेते हैं
इनपुट -
आउटपुट - 7 4 1
इस समस्या को हल करने के लिए, हमें बाइनरी ट्री को पार करना होगा। यह ट्रैवर्सल दो तरह से किया जा सकता है -
प्रीऑर्डर ट्रैवर्सल - यह ट्रैवर्सल रिकर्सन का उपयोग करता है। यहां, हम ट्रैवर्स करेंगे, रूट करेंगे फिर लेफ्ट और फिर राइट सबट्री। यदि हमें कोई लीफ नोड मिलता है तो हम उसे प्रिंट करेंगे, अन्यथा हम नोड के बच्चों की जांच करेंगे और लीफ नोड को खोजने के लिए उन्हें एक्सप्लोर करेंगे।
उदाहरण
हमारे समाधान के कार्यान्वयन को दिखाने के लिए कार्यक्रम -
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
Node* insertNode(int data) {
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
void findLeafNode(Node* root) {
if (!root)
return;
if (!root->left && !root->right) {
cout<<root->data<<"\t";
return;
}
if (root->right)
findLeafNode(root->right);
if (root->left)
findLeafNode(root->left);
}
int main() {
Node* root = insertNode(21);
root->left = insertNode(5);
root->right = insertNode(11);
root->left->left = insertNode(8);
root->left->right = insertNode(98);
root->right->left = insertNode(2);
root->right->right = insertNode(8);
cout<<"Leaf nodes of the tree from right to left are:\n";
findLeafNode(root);
return 0;
} आउटपुट
Leaf nodes of the tree from right to left are − 18 2 98 8. हैं
पोस्टऑर्डर ट्रैवर्सल - लीफ नोड को खोजने के लिए यह ट्रैवर्सल पुनरावृत्ति का उपयोग करेगा। हम डेटा को स्टोर करने के लिए स्टैक का उपयोग करेंगे और पेड़ को पोस्टऑर्डर तरीके से पार करेंगे (पहले दायां उपट्री फिर बाएं सबट्री और फिर रूट) और लीफ नोड्स प्रिंट करें।
उदाहरण
हमारे समाधान के कार्यान्वयन को दिखाने के लिए कार्यक्रम -
#include<bits/stdc++.h>
using namespace std;
struct Node {
Node* left;
Node* right;
int data;
};
Node* insertNode(int key) {
Node* node = new Node();
node->left = node->right = NULL;
node->data = key;
return node;
}
void findLeafNode(Node* tree) {
stack<Node*> treeStack;
while (1) {
if (tree) {
treeStack.push(tree);
tree = tree->right;
} else {
if (treeStack.empty())
break;
else {
if (treeStack.top()->left == NULL) {
tree = treeStack.top();
treeStack.pop();
if (tree->right == NULL)
cout<<tree->data<<"\t";
}
while (tree == treeStack.top()->left) {
tree = treeStack.top();
treeStack.pop();
if (treeStack.empty())
break;
}
if (!treeStack.empty())
tree = treeStack.top()->left;
else
tree = NULL;
}
}
}
}
int main(){
Node* root = insertNode(21);
root->left = insertNode(5);
root->right = insertNode(11);
root->left->left = insertNode(8);
root->left->right = insertNode(98);
root->right->left = insertNode(2);
root->right->right = insertNode(18);
cout<<"Leaf nodes of the tree from right to left are:\n";
findLeafNode(root);
return 0;
} आउटपुट
Leaf nodes of the tree from right to left are − 18 2 98 8. हैं