মরিস ইনর্ডার ট্র্যাভারসাল


কাঠিন্য মাত্রা মধ্যম
গাছ ট্রি ট্রভারসাল

আমরা একটি গাছ পেরোতে পারেন ক্রমানুসারে পুনরাবৃত্তি ফ্যাশন ব্যবহার করে গাদা, কিন্তু এটি স্থান গ্রহণ করে। সুতরাং, এই সমস্যায়, আমরা লিনিয়ার স্পেস ব্যবহার না করে একটি গাছকে ট্র্যাভার করতে যাচ্ছি। এই ধারণাটিকে বাইনারি গাছগুলিতে মরিস ইনর্ডার ট্র্যাভারসাল বা থ্রেডিং বলা হয়।

উদাহরণ

          2

       /      \

     1           3

  /      \

4          5
4 1 5 2 3
       3

    /      \

  1          4
            
          /      \
 
        2          5
1 3 2 4 5

অভিগমন

ধারণাটি হ'ল: আমরা যদি কোনও স্ট্যাকের জায়গা (বা পুনর্বিবেচনার সহায়তার জায়গা) ছাড়াই গাছটিকে অতিক্রম করতে পারি তবে আমরা যদি কোনও নোডের ঠিকানা হারাবেন না আমরা তাদের স্মৃতিতে সংরক্ষণ না করে আগে গিয়েছিলাম। এই পদ্ধতির বলা হয় মরিস ইনর্ডার ট্র্যাভারসাল.

তবে কোনও জায়গার অনুমতি না থাকলে কীভাবে নোডের ঠিকানা সঞ্চয় করা যায়? গাছের কাঠামোটি এমনভাবে পরিবর্তন করার ধারণাটি হ'ল মূল নোড থেকে একটি সাবট্রির কয়েকটি নির্দিষ্ট নোড দেখার পরে, আমরা তার অন্যান্য সাবট্রি প্রক্রিয়া করার জন্য মূল নোডে ফিরে যেতে পারি। বলুন আমরা বাম সাবট্রি সম্পূর্ণ পরিদর্শন করেছি এবং আবার বাম সাবট্রির কোনও নোড থেকে আবার মূলটিতে একটি পয়েন্টার যুক্ত করেছি। এখন, আমরা মূল মূলটিতে ফিরে এসে সঠিক সাবট্রিটি প্রক্রিয়া করতে পারি। মরিস ইনর্ডার ট্র্যাভারসালে, আমরা কোনও মূলের (তার বাম সাবট্রিতে) আন্ডারআর্ডার পূর্বসূরিটিকে নিজের সাথে সংযুক্ত করি।

মরিস ইনঅর্ডার ট্র্যাভারসাল সি ++ টিউটোরিয়াল

পয়েন্টার যুক্ত করার এই প্রক্রিয়া (থ্রেড) অন্তর্বর্তী পূর্বসূরীর থেকে মূল পর্যন্ত ডাকা হয় থ্রেডিং। আবার, আমরা গাছের কাঠামোকে বিরক্ত করতে চাই না, তাই আমরা একটি অ্যালগরিদম ডিজাইন করব যা লিঙ্কগুলি স্বয়ংক্রিয়ভাবে মুছে ফেলবে এবং অপরিবর্তিত গাছ এর মূল কাঠামো ধরে রাখুন.

অ্যালগরিদম

  1. গাছের মূল হিসাবে বর্তমান নোডের সূচনা করুন।
  2. যতক্ষণ না আমরা সেই অবস্থায় পৌঁছাচ্ছি ততক্ষণ পুনরাবৃত্তি করুন বর্তমান নোড হয়ে খালি. 
    • যদি বাম বর্তমান মূলের সাবট্রিটি হ'ল শূন্য :
        • আমরা এখন রুটটি মুদ্রণ করতে এবং ডান সাবট্রিতে চলে যেতে পারি, সুতরাং কারেন্টনোড = কারেন্টনোড-> ডানদিকে।
    • যদি বাম বর্তমান মূলের সাবট্রিটি হ'ল  না শূন্য :
        • এই ক্ষেত্রে, আমরা অপরিবর্তিত / থ্রেড বর্তমান নোডের নিজের বাম সাবট্রি (আন্ডারর্ডার পূর্বসূরী) এর ডানদিকের নোড
            • অস্থায়ী = কারেন্টোড-> বাম;
            • যদিও টেম্প-> ডান হয় না শূন্য বা অস্থায়ী হয় বর্তমান নয়
              • temp = টেম্প-> ডান
        • যদি অস্থায়ী-> ঠিক হয় শূন্য:
            • হিসাবে থ্রেডিং অপসারণ temp-> ডান = NULL
            • ডান সাবট্রি, কারেন্টনোড = কারেন্টনোড-> ডানদিকে প্রক্রিয়া করুন
        • যদি অস্থায়ী-> ঠিক হয় নাল না:
            • এই নোড হিসাবে থ্রেড টেম্প-> ডান = কারেন্ট নোড
            • বাম সাবট্রিটি এখনই প্রক্রিয়া করুন, কারেন্টনোড = কারেন্টনোড-> বামে

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

সি ++ প্রোগ্রাম

#include <bits/stdc++.h>

using namespace std;

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


void morrisInorder(treeNode* &root)
{
    treeNode* currentNode = root;
    while(currentNode != NULL)
    {
        if(currentNode->left == NULL)
        {
            cout << currentNode->value << " ";
            currentNode = currentNode->right;
        }
        else
        {
            treeNode* temp = currentNode->left;
            while((temp->right != NULL) && (temp->right != currentNode))
                temp = temp->right;

            if(temp->right == NULL)
            {
                temp->right = currentNode;
                //threading
                currentNode = currentNode->left;
            }
            else
            {
                cout << currentNode->value << " ";
                temp->right = NULL;
                //unthreading
                currentNode = currentNode->right;
            }
        }
    }
}

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);

    morrisInorder(root);
    return 0;
}
4 1 5 2 3

জাভা প্রোগ্রাম

class treeNode
{
    int value;
    treeNode left, right;

    public treeNode(int x)
    {
        value = x;
        left = right = null;
    }
}

class BinaryTree
{
    treeNode root;
    void MorrisInorder()
    {
        treeNode currentNode = root;

        while(currentNode != null)
        {
            if(currentNode.left == null)
            {
                System.out.print(currentNode.value + " ");
                currentNode = currentNode.right;
            }
            else
            {
                treeNode temp = currentNode;
                while(temp.right != null && temp.right != currentNode)
                    temp = temp.right;

                if(temp.right == null)
                {
                    temp.right = currentNode;
                    currentNode = currentNode.left;
                }
                else
                {
                    temp.right = null;
                    System.out.print(currentNode.value + " ");
                    currentNode = currentNode.right;
                }
            }
        }

    }

    public static void main(String args[])
    {
        BinaryTree tree = new BinaryTree();
        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.MorrisInorder();
    }
}
4 1 5 2 3

মরিস ইনর্ডার ট্র্যাভারসাল সম্পর্কিত জটিলতা বিশ্লেষণ

সময় জটিলতা

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

স্পেস জটিলতা ity

ও (1), যেমন আমরা কিছু ভেরিয়েবল ঘোষণার জন্য ধ্রুবক স্পেস ব্যবহার করি use তবে, অন্য কোনও সহায়ক স্থান কোনও উদ্দেশ্যে ব্যবহার করা হয় না। মরিস ইনর্ডার ট্র্যাভারসাল এই বিষয়ে প্রতিশ্রুতি দেয়।