मोरिस आन्तरिक ट्रैभर्सल


कठिनाई तह मध्यम
ट्री रूख ट्राभर्सल

हामी रूखमा पार गर्न सक्छौं inorder फेसन पुनरावृत्तिक रूपमा, प्रयोग गर्दै स्ट्याक, तर यसले ठाउँ खपत गर्दछ। त्यसोभए, हामी यस समस्यामा लिखीय ठाउँ प्रयोग नगरी रूख पार गर्न गइरहेका छौं। यस अवधारणालाई मोरिस ईन्डर ट्रभर्सल वा बाइनरी रूखहरूमा थ्रेडि called भनिन्छ।

उदाहरणका

          2

       /      \

     1           3

  /      \

4          5
4 1 5 2 3
       3

    /      \

  1          4
            
          /      \
 
        2          5
1 3 2 4 5

दृष्टिकोण

विचार यो छ: हामी रूखलाई कुनै स्ट्याक (वा रिकर्सि ofको सहयोगी ठाउँ) बिना नै ट्रान्सभर्स गर्न सक्दछौं यदि हामी कुनै नोडको ठेगाना नहटाउनुहोस् हामी पहिले उनीहरूको स्मृतिमा भण्डारण नगरी भ्रमण गर्‍यौं। यो दृष्टिकोण भनिन्छ मोरिस आन्तरिक ट्रैभर्सल.

तर कुनै ठाउँलाई अनुमति बिना, कसरी नोडहरूको ठेगानाहरू भण्डार गर्न सकिन्छ? विचार यो छ कि रूखको संरचना यस्तो तरिकाले बदल्नुपर्दछ कि रूट नोडबाट एउटा उपशीटिका केहि विशेष नोडहरू भ्रमण गरे पछि हामी यसको अर्को सबट्री प्रशोधन गर्न फेरि मूल नोडमा जान सक्दछौं। भन्नुहोस् हामी पूर्ण रूपमा बायाँ सब्ट्री भ्रमण गरेका थियौं, र फेरि मूलमा केही बाँया उपट्रीको नोडबाट सूचक थपेका छौं। अब, हामी मूल जडमा फर्केर सह subtree प्रक्रिया गर्न सक्छौं। मोरिस आन्तरिक ट्रैभर्सलमा हामी एक जराको आन्तरिक पूर्ववर्ती (यसको बायाँ उपशीर्षकमा) लाई आफै लिंक गर्छौं।

मोरिस ईन्टर ट्रैवर्सल C ++ ट्यूटोरियल

पोइन्टर्स थप गर्ने यो प्रक्रिया (थ्रेडहरू) inorder पूर्ववर्ती देखि जड भनिन्छ थ्रेडि।। फेरि, हामी रूखको संरचना बिघ्न चाहँदैनौं, त्यसैले हामी एक एल्गोरिथ्म डिजाइन गर्नेछौं जसले लि automatically्कहरूलाई स्वचालित रूपमा मेटाउँछ र अनथ्रेडहरू रूख गर्न यसको मूल संरचना कायम राख्नुहोस्.

अल्गोरिदम

  1. रूखको जराको रूपमा हालको नोड सुरू गर्नुहोस्।
  2. पुनरावृत्ति गर्नुहोस् जबसम्म हामी कन्डिसनमा पुग्दैनौं हालको नोड बन्छ खाली। 
    • यो भने बाँकी हालको जराको सबट्री हो खाली :
        • हामी अब जरा प्रिन्ट गर्न सक्छौं र दाँया उप-ट्रीमा सार्न सक्छौं, त्यसैले हालको नोड = करेन्टनोड-> दायाँ।
    • यो भने बाँकी हालको जराको सबट्री हो  नहीं खाली :
        • यस अवस्थामा, हामी अपठित / धागा दायाँ नोडको बाँया subtree (inorder पूर्ववर्ती) मा आफैं गर्न
            • अस्थायी = हालको नोड-> बाँया;
            • जबकि अस्थायी-> सहि छ नहीं खाली वा अस्थायी हो हालको नोड छैन
              • अस्थायी = अस्थायी-> सहि
        • यदि अस्थायी-> सहि छ खाली:
            • यस रूपमा थ्रेडि remove हटाउनुहोस् अस्थायी-> सही = NULL
            • सही subtree प्रक्रिया, वर्तमानNode = currentNode-> दायाँ
        • यदि अस्थायी-> सहि छ खाली छैन:
            • यस नोडलाई यस रूपमा थ्रेड गर्नुहोस् अस्थायी-> दायाँ = करेन्टनोड
            • बायाँको सबट्री अब प्रक्रिया गर्नुहोस्, हालको नोड = हालको नोड-> बाँया

मोरिस इनडर ट्रभर्सलको कार्यान्वयन

C ++ कार्यक्रम

#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

जटिलता मोरिस इनडर ट्रभर्सलको विश्लेषण

समय जटिलता

O (N), जहाँ N रूखमा नोडहरूको संख्या हो। यो निश्चित छ कि हामी प्रत्येक नोडलाई ठ्याक्कै २ पटक हेर्दछौं, किनकि ती सबै थ्रेडिंग र अनथ्रेडिंगको प्रक्रियामा छन्। तर, समय जटिलता रैखिक रहन्छ।

ठाउँ जटिलता

O (१), किनकि हामी केहि भ्यारीएबलहरू घोषित गर्नका लागि स्थिर स्थानको प्रयोग गर्छौं। तर, कुनै अन्य सहयोगी ठाउँ कुनै उद्देश्यको लागि प्रयोग गरिदैन। त्यो मोरिस ईन्ट्रो ट्रभर्सलको बारेमा हुन्छ।