C++-এ BST II-তে Inorder Successor

ধরুন আমাদের একটি বাইনারি সার্চ ট্রিতে একটি নোড আছে, আমাদের BST-এ সেই নোডের ইন-অর্ডার উত্তরাধিকারী খুঁজে বের করতে হবে। যদি কোনো ইন-অর্ডার উত্তরসূরি না থাকে, তাহলে শূন্য ফেরত দিন। আমরা জানি যে একটি নোডের উত্তরসূরী হল নোডের মানের চেয়ে ছোট কী সহ নোড।

আমাদের নোডে সরাসরি অ্যাক্সেস থাকবে কিন্তু গাছের মূলে নয়। এখানে প্রতিটি নোডের মূল নোডের একটি রেফারেন্স থাকবে। নিচে নোড-

যদি ইনপুট −

এবং নোড 2 হলে আউটপুট হবে 3।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• যদি নোডের ডানদিকে শূন্য না হয়, তাহলে −

  • নোড :=নোডের ডানদিকে

  • নোডের বাম অংশ শূন্য না হলে −

    করুন

    • নোড :=নোডের বাম

  • রিটার্ন নোড

• যখন (নোডের প্যারেন্ট নাল নয় এবং নোড নোডের প্যারেন্টের বাম দিকে সমান নয়), −

  • নোড :=নোডের প্যারেন্ট

• রিটার্ন নোডের অভিভাবক

উদাহরণ

আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -

#include  namespace ব্যবহার করে std;class Node {পাবলিক:int val; নোড* বাম; নোড* ডান; নোড* প্যারেন্ট; নোড(int v, Node* par =NULL){ val =v; left =NULL; right =NULL; পিতামাতা =par; }};ক্লাস সলিউশন {পাবলিক:নোড* ইনঅর্ডারসুর (নোড* নোড) { যদি (নোড->ডান) { নোড =নোড->ডান; যখন (নোড->বাম) নোড =নোড->বাম; রিটার্ন নোড; } যখন (নোড->প্যারেন্ট &&নোড!=নোড->প্যারেন্ট->বাম) { নোড =নোড->প্যারেন্ট; } return node->parent; }};প্রধান(){সমাধান ob; নোড *রুট =নতুন নোড(5); root->left =new Node(3, root); root->right =new Node(6, root); root->left->left =নতুন নোড(2, root->left); root->left->right =new Node(4, root->left); root->left->left->left =new Node(1, root->left->left); cout <<(ob.inorderSuccessor(root->left->left))->val;}

ইনপুট

নোড *রুট =নতুন নোড(5); রুট->বাম =নতুন নোড(3, রুট); রুট->ডান =নতুন নোড(6, রুট); রুট->বাম->বাম =নতুন নোড( 2, root->left); root->left->right =new Node(4, root->left); root->left->left->left =new Node(1, root->left->left) );(ob.inorderSuccessor(root->left->left))->val

আউটপুট

3