મોરિસ ઇનોર્ડર ટ્રાવર્સલ


મુશ્કેલી સ્તર મધ્યમ
વૃક્ષ વૃક્ષ આડેધડ

અમે એક વૃક્ષ પસાર કરી શકો છો આંતરિક ફેશન પુનરાવર્તિત, ઉપયોગ કરીને સ્ટેક, પરંતુ તે જગ્યા લે છે. તેથી, આ સમસ્યામાં, આપણે લીનીયર સ્પેસનો ઉપયોગ કર્યા વિના ઝાડને પસાર કરીશું. આ ખ્યાલને બાઈનરી ટ્રીમાં મોરિસ ઇનોર્ડર ટ્રાવેર્સલ અથવા થ્રેડિંગ કહેવામાં આવે છે.

ઉદાહરણ

          2

       /      \

     1           3

  /      \

4          5
4 1 5 2 3
       3

    /      \

  1          4
            
          /      \
 
        2          5
1 3 2 4 5

અભિગમ

આનો વિચાર છે: જો આપણે સ્ટેક (અથવા રિકર્ઝનની સહાયક જગ્યા) ની જગ્યા વિના વૃક્ષને વટાવી શકીએ છીએ, જો આપણે કોઈપણ નોડનું સરનામું ગુમાવશો નહીં અમે તેમને મેમરીમાં સ્ટોર કર્યા વિના અગાઉ મુલાકાત લીધી હતી. આ અભિગમ કહેવામાં આવે છે મોરિસ ઇનોર્ડર ટ્રાવર્સલ.

પરંતુ કોઈપણ જગ્યાને મંજૂરી વિના, નોડ્સના સરનામાં કેવી રીતે સંગ્રહિત કરી શકાય છે? વૃક્ષની રચનાને એવી રીતે બદલવાનો વિચાર છે કે, રુટ નોડમાંથી એક સબટ્રીના કેટલાક ચોક્કસ ગાંઠોની મુલાકાત લીધા પછી, અમે તેના અન્ય સબટ્રીની પ્રક્રિયા કરવા માટે રુટ નોડ પર પાછા આવી શકીએ. કહો કે અમે ડાબી સબટ્રીની સંપૂર્ણ મુલાકાત લીધી છે, અને ડાબી સબટ્રીના કેટલાક નોડમાંથી ફરીથી મૂળમાં એક પોઇન્ટર ઉમેરીએ છીએ. હવે, આપણે મૂળ મૂળમાં પાછા આવીને જમણી સબટ્રી પ્રક્રિયા કરી શકીએ છીએ. મોરિસ ઇનોર્ડર ટ્રાવેર્સલમાં, અમે રૂટ (તેની ડાબી સબટ્રીમાં) ની અંતર્ગત પૂર્વવર્તીને પોતાની સાથે જોડીએ છીએ.

મોરિસ ઇનઓર્ડર ટ્રાવેર્સલ સી ++ ટ્યુટોરિયલ

પોઇંટર્સ ઉમેરવાની આ પ્રક્રિયા (સૂત્રો) ઇનઓર્ડર પુરોગામીથી રૂટ કહેવામાં આવે છે થ્રેડીંગ. ફરીથી, અમે ઝાડની રચનાને ખલેલ પહોંચાડવા માંગતા નથી, તેથી અમે એક અલ્ગોરિધમનો ડિઝાઇન કરીશું જે લિંક્સને આપમેળે કાtesી નાખશે અને અજાણ્યા માટે વૃક્ષ તેની મૂળ રચના જાળવી રાખો.

અલ્ગોરિધમ

  1. વર્તમાન નોડને ઝાડના મૂળ તરીકે પ્રારંભ કરો.
  2. જ્યાં સુધી આપણે તે સ્થિતિમાં ન પહોંચીએ ત્યાં સુધી પુનરાવર્તન રાખો વર્તમાન નોડ બને નુ. 
    • જો બાકી વર્તમાન મૂળની સબટ્રી છે NULL :
        • હવે આપણે રુટ પ્રિન્ટ કરી શકીએ છીએ અને જમણી સબટ્રી પર જઈ શકીએ છીએ, તેથી કરંટનોડ = વર્તમાનનોડ-> જમણી.
    • જો બાકી વર્તમાન મૂળની સબટ્રી છે  નથી NULL :
        • આ કિસ્સામાં, અમે અક્ષરહિત / થ્રેડ વર્તમાન નોડની પોતાની તરફ ડાબી સબટ્રી (ઇનઓર્ડર પુરોગામી) માં જમણો નોડ
            • કામચલાઉ = વર્તમાનનોડ-> બાકી;
            • જ્યારે કામચલાઉ-> અધિકાર છે નથી NULL અથવા કામચલાઉ છે વર્તમાન નથી
              • કામચલાઉ = ટેમ્પો-> અધિકાર
        • જો કામચલાઉ-> અધિકાર છે 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 વાર મુલાકાત લઈએ છીએ, કારણ કે તે બધા થ્રેડીંગ અને અનથ્રેડિંગની પ્રક્રિયામાંથી પસાર થાય છે. પરંતુ, સમય જટિલતા રેખીય રહે છે.

અવકાશ જટિલતા

ઓ (1), આપણે કેટલાક ચલો જાહેર કરવા માટે સતત જગ્યા વાપરીએ છીએ. પરંતુ, કોઈ અન્ય સહાયક જગ્યાનો ઉપયોગ કોઈ હેતુ માટે કરવામાં આવતો નથી. મોરિસ ઇનોર્ડર ટ્રversવર્સલ વચન જે તે વિશે છે.