এই সমস্যায়, আমাদের একটি বাইনারি ট্রি এবং নোড দেওয়া হয়েছে। আমাদের কাজ হল বাইনারি ট্রিতে নোডের পোস্টঅর্ডার উত্তরসূরি প্রিন্ট করা।
বাইনারী গাছ একটি বিশেষ ধরনের গাছ যাতে প্রতিটি নোডে সর্বোচ্চ 2টি চাইল্ড নোড থাকতে পারে৷
পোস্টডার ট্রাভার্সাল একটি ট্রি ট্রাভার্সাল টেকনিক, যেখানে প্রথম বাম সাবট্রিটি ডান সাবট্রির চেয়ে এবং মূলটি শেষে ট্রাভার্স করা হয়।
উপরের গাছের পোস্টরডার ট্রাভার্সাল:8 4 2 7 9 6
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক।
ইনপুট − উপরের উদাহরণে বাইনারি ট্রি, node=7
আউটপুট − 9
ব্যাখ্যা − আমরা এটি বাইনারি গাছের পোস্ট-অর্ডার ট্রাভার্সালে দেখতে পাচ্ছি।
এই সমস্যাটি সমাধান করার জন্য, একটি সহজ, সহজ এবং নুবের সমাধান হবে কেবল পোস্টঅর্ডার ট্রাভার্সাল খুঁজে বের করা এবং তারপর ট্র্যাভার্সালের পাশে নম্বরটি প্রিন্ট করা।
কিন্তু আমাদের আরও কার্যকর সমাধান শিখতে হবে,
একটি কার্যকর সমাধান পোস্টঅর্ডার ট্রাভার্সালের উপর কিছু সাধারণ পর্যবেক্ষণ ব্যবহার করে।
-
যেহেতু রুটটি পোস্টঅর্ডার ট্রাভার্সালের শেষ নোড, তাই এর উত্তরসূরী হল NULL৷
-
বর্তমান নোডটি সঠিক শিশু হওয়ার ক্ষেত্রে, প্যারেন্ট নোড একটি উত্তরসূরী৷
৷ -
বর্তমান নোড বাম শিশুর ক্ষেত্রে, তারপর
-
যদি সঠিক ভাইবোন অনুপস্থিত থাকে, উত্তরাধিকারী হল একটি অভিভাবক নোড
-
যদি ডান ভাইবোন থাকে তাহলে হয় নোড বা তার বামতম সন্তান উত্তরাধিকারী।
-
এই পদ্ধতিটি কার্যকর, সময়ের জটিলতা হল O(h), তার গাছের উচ্চতা।
উদাহরণ
আমাদের সমাধানের বাস্তবায়ন দেখানোর জন্য প্রোগ্রাম,
#include <iostream>
using namespace std;
struct Node {
struct Node *left, *right, *parent;
int value;
};
struct Node* insertNode(int value) {
Node* temp = new Node;
temp->left = temp->right = temp->parent = NULL;
temp->value = value;
return temp;
}
Node* findPostorderSuccessor(Node* root, Node* n) {
if (n == root)
return NULL;
Node* parent = n->parent;
if (parent->right == NULL || parent->right == n)
return parent;
Node* curr = parent->right;
while (curr->left != NULL)
curr = curr->left;
return curr;
}
int main(){
struct Node* root = insertNode(6);
root->parent = NULL;
root->left = insertNode(2);
root->left->parent = root;
root->left->left = insertNode(8);
root->left->left->parent = root->left;
root->left->right = insertNode(4);
root->left->right->parent = root->left;
root->right = insertNode(9);
root->right->parent = root;
root->right->left = insertNode(7);
root->right->left->parent = root->right;
root->left->right->left = insertNode(14);
struct Node* successorNode = findPostorderSuccessor(root, root->left->right);
if (successorNode)
cout<<"Postorder successor of "<<root->left->right->value<<" is "<<successorNode->value;
else
cout<<"Postorder successor of "<<root->left->right->value<<" is NULL";
return 0;
} আউটপুট
Postorder successor of 4 is 2
