మోరిస్ ఇనార్డర్ ట్రావెర్సల్


కఠినత స్థాయి మీడియం
ట్రీ చెట్టు ట్రావెర్సల్

మేము ఒక చెట్టును దాటవచ్చు క్రమంలో ఫ్యాషన్ పునరావృతంగా, ఉపయోగించడం స్టాక్, కానీ ఇది స్థలాన్ని వినియోగిస్తుంది. కాబట్టి, ఈ సమస్యలో, మేము సరళ స్థలాన్ని ఉపయోగించకుండా చెట్టును దాటబోతున్నాము. ఈ భావనను బైనరీ చెట్లలో మోరిస్ ఇన్ఆర్డర్ ట్రావెర్సల్ లేదా థ్రెడింగ్ అంటారు.

ఉదాహరణ

          2

       /      \

     1           3

  /      \

4          5
4 1 5 2 3
       3

    /      \

  1          4
            
          /      \
 
        2          5
1 3 2 4 5

అప్రోచ్

ఆలోచన ఏమిటంటే: మనం ఉంటే చెట్టును స్టాక్ (లేదా పునరావృత సహాయక స్థలం) లేకుండా ప్రయాణించవచ్చు. ఏ నోడ్ యొక్క చిరునామాను కోల్పోకండి మేము వాటిని మెమరీలో నిల్వ చేయకుండా ముందే సందర్శించాము. ఈ విధానాన్ని అంటారు మోరిస్ ఇనార్డర్ ట్రావెర్సల్.

కానీ ఖాళీ లేకుండా, నోడ్ల చిరునామాలను ఎలా నిల్వ చేయవచ్చు? చెట్టు యొక్క నిర్మాణాన్ని ఈ విధంగా మార్చాలనే ఆలోచన ఉంది, రూట్ నోడ్ నుండి ఒక సబ్‌ట్రీ యొక్క కొన్ని ప్రత్యేకమైన నోడ్‌లను సందర్శించిన తరువాత, దాని ఇతర సబ్‌ట్రీని ప్రాసెస్ చేయడానికి మేము రూట్ నోడ్‌కు తిరిగి రావచ్చు. మేము ఎడమ సబ్‌ట్రీని పూర్తిగా సందర్శించామని చెప్పండి మరియు ఎడమ సబ్‌ట్రీ యొక్క కొన్ని నోడ్ నుండి మళ్లీ మూలానికి పాయింటర్‌ను జోడించండి. ఇప్పుడు, అసలు మూలానికి తిరిగి రావడం ద్వారా సరైన సబ్‌ట్రీని ప్రాసెస్ చేయవచ్చు. మోరిస్ ఇనార్డర్ ట్రావెర్సల్‌లో, మేము రూట్ యొక్క ఇనార్డర్ పూర్వీకుడిని (దాని ఎడమ సబ్‌ట్రీలో) దానితో అనుసంధానిస్తాము.

మోరిస్ ఇనార్డర్ ట్రావెర్సల్ సి ++ ట్యుటోరియల్

పాయింటర్లను జోడించే ఈ ప్రక్రియ (థ్రెడ్లు) inorder పూర్వీకుల నుండి రూట్ వరకు అంటారు థ్రెడింగ్. మళ్ళీ, మేము చెట్టు యొక్క నిర్మాణానికి భంగం కలిగించకూడదనుకుంటున్నాము, కాబట్టి మేము లింక్‌లను స్వయంచాలకంగా తొలగించే అల్గారిథమ్‌ను రూపొందిస్తాము మరియు unthreads చెట్టు దాని అసలు నిర్మాణాన్ని నిలుపుకోండి.

అల్గారిథం

  1. ప్రస్తుత నోడ్‌ను చెట్టు యొక్క మూలంగా ప్రారంభించండి.
  2. మేము ఉన్న స్థితికి చేరుకునే వరకు మళ్ళించండి ప్రస్తుత నోడ్ అవుతుంది శూన్య. 
    • అయితే ఎడమ ప్రస్తుత మూలం యొక్క ఉపశీర్షిక NULL :
        • మనం ఇప్పుడు మూలాన్ని ప్రింట్ చేసి కుడి సబ్‌ట్రీకి తరలించవచ్చు, కాబట్టి currentNode = currentNode-> right.
    • అయితే ఎడమ ప్రస్తుత మూలం యొక్క ఉపశీర్షిక  కాదు NULL :
        • ఈ సందర్భంలో, మేము అన్‌ట్రెడ్ / థ్రెడ్ ప్రస్తుత నోడ్ యొక్క ఎడమ సబ్‌ట్రీ (ఇనార్డర్ పూర్వీకుడు) లోని కుడివైపు నోడ్
            • temp = currentNode-> ఎడమ;
            • అయితే టెంప్-> కుడి కాదు NULL లేదా తాత్కాలికం ప్రస్తుత నోడ్ కాదు
              • temp = temp-> కుడి
        • తాత్కాలిక-> కుడి ఉంటే NULL:
            • థ్రెడింగ్‌ను తొలగించండి temp-> right = NULL
            • కుడి సబ్‌ట్రీని ప్రాసెస్ చేయండి, currentNode = currentNode-> right
        • తాత్కాలిక-> కుడి ఉంటే శూన్యమైనది కాదు:
            • ఈ నోడ్‌ను థ్రెడ్ చేయండి temp-> right = currentNode
            • ప్రస్తుత సబ్‌ట్రీని ఇప్పుడే ప్రాసెస్ చేయండి, currentNode = currentNode-> left

మోరిస్ ఇనార్డర్ ట్రావెర్సల్ అమలు

సి ++ ప్రోగ్రామ్

#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), మేము కొన్ని వేరియబుల్స్ ప్రకటించడానికి స్థిరమైన స్థలాన్ని ఉపయోగిస్తాము. కానీ, ఏ ఇతర ప్రయోజనం కోసం ఏ ఇతర సహాయక స్థలాన్ని ఉపయోగించరు. మోరిస్ ఇన్ఆర్డర్ ట్రావెర్సల్ దాని గురించి వాగ్దానం చేసింది.