প্রোগ্রামটি একটি বাইনারি গাছের পাতার নোডগুলিকে বাম থেকে ডানে প্রিন্ট করতে হবে কিন্তু চ্যালেঞ্জটি শুধুমাত্র একটি স্ট্যাক ব্যবহার করা জড়িত৷
push() ফাংশনের মাধ্যমে বাইনারি গাছের নোড সন্নিবেশ করান এবং পপ() অপারেশনের মাধ্যমে লিফ নোডগুলি প্রদর্শন করা হয়।
লিফ নোড হল শেষ নোড যার বাম এবং ডান পয়েন্টার হল NULL যার মানে সেই নির্দিষ্ট নোডটি প্যারেন্ট নোড নয়৷
উদাহরণ
Input : 12 21 32 41 59 33 70 Output : 41 59 33 70
স্ট্যাক হল একটি ডাটা স্ট্রাকচার যা একটি LIFO স্ট্রাকচার যেখানে শীর্ষ পয়েন্টারটি সন্নিবেশিত শেষ উপাদানগুলির দিকে নির্দেশ করবে যাতে লিফ নোডগুলি শেষ পর্যন্ত স্ট্যাকের মধ্যে ঢোকানো হবে এবং সেগুলি অন্য কোনও নোডের আগে স্ট্যাক থেকে পপ আউট বা সরানো হবে। স্ট্যাক গঠন প্রতি।
নিচের কোডটি প্রদত্ত অ্যালগরিদমের STL ব্যবহার করে C++ বাস্তবায়ন দেখায়।
অ্যালগরিদম
START Step 1 -> create node variable of type structure Declare int data Declare pointer of type node using *left, *right Step 2 -> create function for inserting node with parameter as val Declare node variable of node using malloc Set node->data = val Set node->left = node->right = NULL return node step 3 -> Declare Function void leaf(Node *ptr) create vector stack<Node*>stck Loop While 1 IF ptr Stck.push(ptr) Ptr = ptr->left Else IF (stck.empty()) Break Else IF (stck.top()->right == NULL) Set ptr = stck.top() Set stck.pop() IF ptr->left = NULL Print ptr->data End Loop While ptr == stck.top()->right Set ptr = stck.top() Call stck.pop() IF stck.empty() Break End IF !stck.empty() Set ptr = tck.top()->right Else Set ptr = NULL EndIF End End End Step 4-> In main() Call New passing value user want to insert as Node* root = New(12) Call leaf(root) STOP
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
// Structure of a node
struct Node {
Node* left;
Node* right;
int data;
};
//Function to create a new node
Node* New(int val) {
Node* node = new Node();
node->left = node->right = NULL;
node->data = val;
return node;
}
// leaf node using stack
void leaf(Node* ptr) {
// stack that will store nodes
stack<Node*> stck;
while (1) {
if (ptr) {
stck.push(ptr);
ptr = ptr->left;
} else {
if (stck.empty())
break;
else {
if (stck.top()->right == NULL) {
ptr = stck.top();
stck.pop();
// Print the leaf node
if (ptr->left == NULL)
printf("%d ", ptr->data);
}
while (ptr == stck.top()->right) {
ptr = stck.top();
stck.pop();
if (stck.empty())
break;
}
if (!stck.empty())
ptr = stck.top()->right;
else
ptr = NULL;
}
}
}
}
int main() {
printf("leaf nodes at end level are : ");
Node* root = New(12);
root->left = New(21);
root->right = New(32);
root->left->left = New(41);
root->left->right = New(59);
root->right->left = New(33);
root->right->right = New(70);
leaf(root);
return 0;
} আউটপুট
যদি আমরা উপরের প্রোগ্রামটি চালাই তবে এটি নিম্নলিখিত আউটপুট তৈরি করবে।
leaf nodes at end level are : 41 59 33 70
