மோரிஸ் இன்டர் ஆர்டர் டிராவர்சல்


சிரமம் நிலை நடுத்தர
மரம் மரம் பயணம்

நாம் ஒரு மரத்தில் பயணிக்க முடியும் ஆணைப்படி ஃபேஷன் மீண்டும், பயன்படுத்தி ஸ்டாக், ஆனால் அது இடத்தைப் பயன்படுத்துகிறது. எனவே, இந்த சிக்கலில், நேரியல் இடம் பயன்படுத்தப்படாமல் ஒரு மரத்தை நாம் பயணிக்கப் போகிறோம். இந்த கருத்து பைனரி மரங்களில் மோரிஸ் இன்டர் ஆர்டர் டிராவர்சல் அல்லது த்ரெடிங் என்று அழைக்கப்படுகிறது.

உதாரணமாக

          2

       /      \

     1           3

  /      \

4          5
4 1 5 2 3
       3

    /      \

  1          4
            
          /      \
 
        2          5
1 3 2 4 5

அணுகுமுறை

யோசனை என்னவென்றால்: நாம் இருந்தால் ஒரு அடுக்கின் இடம் இல்லாமல் (அல்லது மறுநிகழ்வின் துணை இடம்) இல்லாமல் மரத்தை பயணிக்க முடியும் எந்த முனையின் முகவரியையும் இழக்காதீர்கள் அவற்றை நினைவகத்தில் சேமிக்காமல் நாங்கள் முன்பு பார்வையிட்டோம். இந்த அணுகுமுறை அழைக்கப்படுகிறது மோரிஸ் இன்டர் ஆர்டர் டிராவர்சல்.

ஆனால் எந்த இடமும் அனுமதிக்கப்படாமல், ஒருவர் எவ்வாறு முனைகளின் முகவரிகளை சேமிக்க முடியும்? மரத்தின் கட்டமைப்பை அவ்வாறு மாற்றுவதே இதன் யோசனை, ரூட் முனையிலிருந்து ஒரு சப்டிரீயின் சில குறிப்பிட்ட முனைகளைப் பார்வையிட்ட பிறகு, அதன் பிற சப்டிரீயைச் செயலாக்க ரூட் முனைக்குத் திரும்பலாம். நாங்கள் இடது சப்டிரீயை முழுவதுமாக பார்வையிட்டோம் என்று சொல்லுங்கள், இடது சப்டிரீயின் சில முனையிலிருந்து ஒரு சுட்டிக்காட்டி மீண்டும் வேரில் சேர்க்கவும். இப்போது, ​​அசல் மூலத்திற்கு வருவதன் மூலம் சரியான சப்டிரீயை செயலாக்கலாம். மோரிஸ் இன்டர் ஆர்டர் டிராவர்சலில், ஒரு வேரின் (அதன் இடது சப்டிரீயில்) முன்னோடி முன்னோடிக்கு தன்னை இணைக்கிறோம்.

மோரிஸ் இன்டர் டிராவர்சல் சி ++ டுடோரியல்

சுட்டிகள் சேர்க்கும் செயல்முறை (இழைகள்) inorder முன்னோடி முதல் வேர் வரை அழைக்கப்படுகிறது த்ரெட்டிங். மீண்டும், மரத்தின் கட்டமைப்பைத் தொந்தரவு செய்ய நாங்கள் விரும்பவில்லை, எனவே இணைப்புகளை தானாகவே நீக்கும் ஒரு வழிமுறையை வடிவமைப்போம் unthreads மரம் அதன் அசல் கட்டமைப்பைத் தக்க வைத்துக் கொள்ளுங்கள்.

அல்காரிதம்

  1. தற்போதைய முனையை மரத்தின் வேராகத் தொடங்கவும்.
  2. நாம் இருக்கும் நிலையை அடையும் வரை மீண்டும் செயல்படுங்கள் தற்போதைய முனை ஆகிறது ஏதுமில்லை. 
    • என்றால் விட்டு தற்போதைய மூலத்தின் துணை மரம் சுழியாக :
        • நாம் இப்போது ரூட்டை அச்சிட்டு வலது சப் ட்ரீக்கு செல்லலாம், எனவே currentNode = currentNode-> right.
    • என்றால் விட்டு தற்போதைய மூலத்தின் துணை மரம்  இல்லை சுழியாக :
        • இந்த விஷயத்தில், நாங்கள் unthread / thread தற்போதைய முனையின் இடது சப்டிரீ (வலதுபுற முன்னோடி) இல் வலதுபுற முனை
            • temp = currentNode-> இடது;
            • போது temp-> சரி இல்லை சுழியாக அல்லது தற்காலிகமானது நடப்புநொட் இல்லை
              • temp = temp-> சரி
        • தற்காலிக-> சரியானது என்றால் சுழியாக:
            • என த்ரெடிங்கை அகற்று temp-> right = NULL
            • சரியான துணை மரத்தை செயலாக்கவும், currentNode = currentNode-> வலது
        • தற்காலிக-> சரியானது என்றால் இல்லை:
            • இந்த முனையை நூல் 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), சில மாறிகள் அறிவிக்க நிலையான இடத்தைப் பயன்படுத்துகிறோம். ஆனால், வேறு எந்த துணை இடமும் எந்த நோக்கத்திற்காகவும் பயன்படுத்தப்படுவதில்லை. மோரிஸ் இன்டர் டிராவர்ஸல் அதைப் பற்றி உறுதியளிக்கிறது.