একটি বাইনারি ট্রি দেওয়া আছে, আমাদের এর লিফ নোডগুলো প্রিন্ট করতে হবে এবং তারপর সেই লিফ নোডগুলো রিমুভ করতে হবে এবং এটি পুনরাবৃত্তি করব যতক্ষণ না ট্রিতে কোনো নোড থাকে।
উদাহরণ
সুতরাং সমস্যার আউটপুট হওয়া উচিত −
6 7 9 13 14 3 4 2 1
অ্যাপ্রোচ
আমরা একটি অ্যাপ্রোচ গ্রহণ করেছি যেখানে আমরা DFS প্রয়োগ করছি।
DFS প্রয়োগের জন্য একটি টেম্পোরারি ভ্যালু শূন্য প্রতিটি ভ্যালুর জন্য অ্যাসাইন করা হয় এবং তারপর সব নোডকে maximum(উভয় চাইল্ডের ভ্যালু)+1 অ্যাসাইন করা হয়।
অ্যালগরিদম
START STEP 1→ DEFINE A struct Node WITH DATA MEMBERS data, order, *left, *right STEP 2→ DEFINE A struct Node* newNode(int data, int order) WITH struct Node* node = new Node, node->data = data, node->order = order, node->left = NULL, node->right = NULL, return (node) FUNCTION void postod(struct Node* node, vector<pair<int, int> >& v) STEP 1→ IF node == NULL THEN, RETURN STEP 2→ CALL FUNCTION postod(node->left, v) STEP 3→ CALL FUNCTION postod(node->right, v) STEP 4→ IF node->right == NULL && node->left == NULL THEN, SET node->order AS 1 v.push_back(make_pair(node->order, node->data)) ELSE node->order = max((node->left)->order, (node->right)->order) + 1 v.push_back(make_pair(node->order, node->data)) END IF FUNCTION void printLeafNodes(int n, vector<pair<int, int> >& v) STEP 1→ sort(v.begin(), v.end()) STEP 2→ LOOP FOR i = 0 AND i < n AND i++ IF v[i].first == v[i + 1].first THEN, PRINT v[i].second ELSE PRINT v[i].second END IF END FOR IN main() STEP 1→ CREATE A ROOT NODE LIKE struct Node* root = newNode(8, 0) STEP 2→ DECLARE AND SET n = 9 STEP 3→ CALL postod(root, v); STEP 4→ CALL printLeafNodes(n, v);
উদাহরণ
#include <bits/stdc++.h> using namespace std; struct Node { int data; int order; struct Node* left; struct Node* right; }; struct Node* newNode(int data, int order){ struct Node* node = new Node; node->data = data; node->order = order; node->left = NULL; node->right = NULL; return (node); } void postod(struct Node* node, vector<pair<int, int> >& v){ if (node == NULL) return; /* first recur on left child */ postod(node->left, v); /* now recur on right child */ postod(node->right, v); // If current node is leaf node, it's order will be 1 if (node->right == NULL && node->left == NULL) { node->order = 1; // make pair of assigned value and tree value v.push_back(make_pair(node->order, node->data)); } else { node->order = max((node->left)->order, (node->right)->order) + 1; v.push_back(make_pair(node->order, node->data)); } } void printLeafNodes(int n, vector<pair<int, int> >& v){ sort(v.begin(), v.end()); for (int i = 0; i < n; i++) { if (v[i].first == v[i + 1].first) cout << v[i].second << " "; else cout << v[i].second << "\n"; } } int main(){ struct Node* root = newNode(1, 0); root->left = newNode(2, 0); root->right = newNode(3, 0); root->left->left = newNode(4, 0); root->left->right = newNode(6, 0); root->right->left = newNode(14, 0); root->right->right = newNode(9, 0); root->left->left->left = newNode(7, 0); root->left->left->right = newNode(13, 0); int n = 9; vector<pair<int, int> > v; postod(root, v); printLeafNodes(n, v); return 0; }
আউটপুট
এই প্রোগ্রাম আউটপুট প্রিন্ট করবে −
6 7 9 13 14 3 4 2 1
