বাইনারি গাছের আইট্রেটিভ ইনর্ডার ট্র্যাভারসাল


কাঠিন্য মাত্রা মধ্যম
বাইনারি ট্রি ট্রি ট্রভারসাল

"বাইনারি ট্রি এর আইট্রেটিভ ইনর্ডার ট্র্যাভারসাল" সমস্যাটিতে আমাদের একটি দেওয়া হয় বাইনারি গাছ। আমাদের এটি ইনর্ডার ফ্যাশনে যেতে হবে "পুনরাবৃত্তি", পুনরাবৃত্তি ছাড়া।

উদাহরণ

                 2

              /     \

            1         3

          /   \

        4       5                

4 1 5 2 3
           1 
 
         /    \

       2        3

     /            \

    4               6

                      \

                        7

4 2 1 3 6 7

অ্যালগরিদম

  1. একটি পরিবর্তনশীল সূচনা "কার্নোড" বাইনারি গাছের মূল হিসাবে
  2. একটি খালি স্ট্যাক শুরু করুন, নোডযুক্ত তারা যেমন পথভ্রষ্ট হয়
  3. স্ট্যাকটি খালি না হওয়া বা না হওয়া অবধি নিম্নলিখিতটি করুন কার্নোড হয়ে উঠেনি খালি:
    • যদিও কার্নোড is না খালি:
      1. ধাক্কা কার্নোড স্ট্যাকের মধ্যে
      2. বর্তমান নোড হিসাবে পরিবর্তন করে বামতম সন্তানের দিকে যেতে থাকুন কার্নোড = কার্নোড-> বাম
    • এখন, স্ট্যাকের উপরের নোডটি বর্তমান সাবট্রির সবচেয়ে বাম নোড, সুতরাং আমরা স্ট্যাকের উপরের নোডের মানটি মুদ্রণ করব
    • দায়িত্ব অর্পণ করা কার্নোড স্ট্যাকের উপরের নোডের সঠিক সন্তান হিসাবে কার্নোড = স্ট্যাক.টপ () -> ডান 
    • বর্তমান নোড হিসাবে পরিবর্তন করে বামতম সন্তানের দিকে যেতে থাকুন কার্নোড = কার্নোড-> বাম এই বামতম নোডের ডান সাবট্রি প্রক্রিয়া করতে
    • স্ট্যাকের বাইরে কোনও উপাদান পপ করুন

ব্যাখ্যা

প্রোগ্রামটি স্ট্যাকটি সর্বাধিক সাম্প্রতিক উপাদানটিকে পপ করে এই ধারণাটি ব্যবহার করে, উপরে বর্ণিত অ্যালগরিদমে আমরা কেবলমাত্র অনুমান করি যে যদি বর্তমান নোড (যা প্রাথমিকভাবে মূলটির মূল) বৃক্ষ) এর একটি বাম শিশু রয়েছে, তারপরে আমরা আর তার বাম শিশুটিকে স্ট্যাকের মধ্যে চাপ দিই যতক্ষণ না আর কোনও বাম বাচ্চা না থাকে remain

যখন কেসটি দেখা দেয় যে বর্তমান নোডের বাম বাচ্চা নেই, এটি স্পষ্ট যে স্ট্যাকের উপরের নোডটি "অতি সম্প্রতি বামতম নোড" যুক্ত। সুতরাং, এটি ট্র্যাভারসাল বাকি ক্রমে প্রথম আসা উচিত। সুতরাং, আমরা আমাদের অর্ডার তালিকায় এটি মুদ্রণ / যুক্ত করা শুরু করি এবং এটিকে স্ট্যাকের বাইরে আউট করি। একবার হয়ে গেলে, আমরা এখন যে বিষয়টি সম্পর্কে পরিষ্কার বাম-কার্নোড-রাইট (অভ্যন্তরীণ ক্রম), বাম এবং নোড অংশ বিভ্রান্ত হয়। সুতরাং, নোডের ডান সাবট্রি প্রক্রিয়াটির মধ্যে রয়েছে!

স্বজ্ঞাতভাবে, যেহেতু আমরা বর্তমান নোডের ডান সাবট্রিতে একই প্রক্রিয়াটি প্রয়োগ করতে চাই, তাই আমরা এটিকে সাধারণকরণ করতে পারি: কার্নোড = কার্নোড-> ডান।

বাইনারি গাছের আইট্রেটিভ ইনর্ডার ট্র্যাভারসাল

বাস্তবায়ন

বাইনারি গাছের আইট্রেটিভ ইনর্ডার ট্র্যাভারসাল এর সি ++ প্রোগ্রাম

#include <bits/stdc++.h>

using namespace std;

struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};



void iterativeInorder(treeNode* root)
{
    stack <treeNode*> ;
    treeNode* curNode = root;elements

    while(curNode != NULL || !elements.empty())
    {
        while(curNode != NULL)
        {
            elements.push(curNode);
            curNode = curNode->left;
        }


        cout << elements.top()->value << " ";
        curNode = elements.top()->right;
        elements.pop();
    }
}


int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(1);
    root->right = new treeNode(3);
    root->left->left = new treeNode(4);
    root->left->right = new treeNode(5);

    iterativeInorder(root);
    cout << endl;
    return 0;
}
4 1 5 2 3 

বাইনারি ট্রি এর আইট্রেটিভ ইনর্ডার ট্র্যাভারসাল জাভা প্রোগ্রাম

import java.util.Stack; 
  
class treeNode 
{ 
    int value; 
    treeNode left, right; 
  
    public treeNode(int x) 
    { 
        value= x; 
        left = right = null; 
    } 
} 
  
class Tree 
{ 
    treeNode root; 
    void iterativeInorder() 
    { 
        
        Stack<treeNode> elements = new Stack<treeNode>(); 
        treeNode curNode = root; 
  
        while (curNode != null || !elements.empty()) 
        { 
            while (curNode != null) 
            { 
                elements.push(curNode); 
                curNode = curNode.left; 
            } 
 
            curNode = elements.peek().right;
            System.out.print(elements.peek().value + " ");
            elements.pop();
        } 
    } 
  
    public static void main(String args[]) 
    { 
        Tree tree = new Tree(); 
        tree.root = new treeNode(2); 
        tree.root.left = new treeNode(1); 
        tree.root.left.left = new treeNode(4); 
        tree.root.left.right = new treeNode(5); 
        tree.root.right = new treeNode(3); 
        tree.iterativeInorder(); 
    } 
}
4 1 5 2 3

জটিলতা বিশ্লেষণ

সময় জটিলতা বাইনারি ট্রি এর আইট্রেটিভ ইনর্ডার ট্র্যাভারসাল এর

সময় জটিলতা হয় চালু), যেমন আমরা প্রতিটি নোড ঠিক একবার দেখেছি। এখানে, এন বাইনারি গাছে নোডের সংখ্যা।

স্পেস জটিলতা ity বাইনারি ট্রি এর আইট্রেটিভ ইনর্ডার ট্র্যাভারসাল এর

স্থান জটিলতা হয় চালু). সবচেয়ে খারাপ পরিস্থিতি বিবেচনা করে, যেখানে গাছটি একটি স্কিউড হতে পারে, সেখানে স্থান জটিলতা বাইনারি গাছের নোডের সংখ্যার সমান হবে।