এই সমস্যায়, আমাদের একটি বাইনারি ট্রি দেওয়া হয়েছে এবং আমাদের ডান থেকে বামে বাইনারি গাছের সমস্ত পাতার নোড প্রিন্ট করতে হবে৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক
ইনপুট −
আউটপুট − 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
