මොරිස් ඉනෝඩර් ට්‍රැවර්සල්


දුෂ්කරතා මට්ටම මධ්යම
ගස රුක් සංචලනය

අපට ගසක් හරහා ගමන් කළ හැකිය පිළිවෙළින් විලාසිතා පුනරාවර්තනය, භාවිතා කිරීම අඩුයි, නමුත් එය අවකාශය පරිභෝජනය කරයි. ඉතින්, මෙම ගැටළුව තුළ, අපි රේඛීය අවකාශය භාවිතා නොකර ගසක් හරහා ගමන් කරන්නෙමු. මෙම සංකල්පය ද්විමය ගස්වල මොරිස් ඉනෝඩර් ට්‍රැවර්සල් හෝ නූල් කිරීම ලෙස හැඳින්වේ.

උදාහරණයක්

          2

       /      \

     1           3

  /      \

4          5
4 1 5 2 3
       3

    /      \

  1          4
            
          /      \
 
        2          5
1 3 2 4 5

ප්රවේශය

අදහස නම්: අපට නම් ගසක සිරස් අතට (හෝ පුනරාවර්තනයේ සහායක අවකාශය) නොමැතිව ගමන් කළ හැකිය. කිසිදු නෝඩයක ලිපිනය නැති නොකරන්න මතකයේ ගබඩා නොකර අපි කලින් ගියෙමු. මෙම ප්රවේශය හැඳින්වේ මොරිස් ඉනෝඩර් ට්‍රැවර්සල්.

නමුත් කිසිදු ඉඩක් නොමැතිව, යමෙකුට නෝඩ් වල ලිපින ගබඩා කරන්නේ කෙසේද? මෙහි අදහස නම් ගසෙහි ව්‍යුහය ඒ ආකාරයෙන් වෙනස් කිරීමයි, එනම් මූල නෝඩයේ සිට එක් උප කුලකයක විශේෂිත නෝඩ් කිහිපයක් බැලීමෙන් පසුව, අපට එහි අනෙක් උප කුලකය සැකසීම සඳහා නැවත මූල නෝඩයට යා හැකිය. අපි වම් උප කුලයට සම්පූර්ණයෙන්ම පිවිසුන බව පවසන්න, සහ වම් උප කුලයේ කිසියම් නෝඩයකින් දර්ශකය නැවත මූලයට එක් කරන්න. දැන්, මුල් මූලයට නැවත පැමිණීමෙන් අපට නිවැරදි උප කුලකය සැකසිය හැකිය. මොරිස් ඉනෝඩර් ට්‍රැවර්සල් හි දී, අපි මූලයක අක්‍රීය පූර්වගාමියා (එහි වම් උප කුලයේ) තමා හා සම්බන්ධ කරමු.

මොරිස් ඉනෝඩර් ට්‍රැවර්සල් සී ++ නිබන්ධනය

දර්ශක එකතු කිරීමේ මෙම ක්‍රියාවලිය (නූල්) inorder පූර්වගාමියාගේ සිට root දක්වා හැඳින්වේ නූල් දැමීම. නැවතත්, ගසෙහි ව්‍යුහයට බාධා කිරීමට අපට අවශ්‍ය නැත, එබැවින් අපි සබැඳි ස්වයංක්‍රීයව මකා දැමිය හැකි ඇල්ගොරිතමයක් නිර්මාණය කරමු නොකැඩූ ගස එහි මුල් ව්‍යුහය රඳවා ගන්න.

ඇල්ගොරිතම

  1. ගසෙහි මුල ලෙස වත්මන් නෝඩය ආරම්භ කරන්න.
  2. අප සිටින තත්වයට ළඟා වන තුරු නැවත නැවත ක්‍රියා කරන්න වත්මන් නෝඩය වන්න NULL. 
    • නම් වම් වත්මන් මූලයේ උප කුලකය වේ NULL :
        • අපට දැන් root මුද්‍රණය කර දකුණු උප කුලයට ගමන් කළ හැකිය, එබැවින් currentNode = currentNode-> දකුණ.
    • නම් වම් වත්මන් මූලයේ උප කුලකය වේ  නැත NULL :
        • මේ අවස්ථාවේ දී, අපි නූල් / නූල් වත්මන් නෝඩයේ වම් උප කුලයේ (අක්‍රීය පූර්වගාමියා) දකුණු කෙළවරේ නෝඩය තමාටම
            • temp = currentNode-> වම;
            • අතර temp-> හරි නැත NULL හෝ තාවකාලිකයි වත්මන් නෝඩ් නොවේ
              • temp = temp-> හරි
        • තාවකාලික-> හරි නම් NULL:
            • නූල් ඉවත් කරන්න temp-> right = NULL
            • දකුණු උප කුලකය සකසන්න, currentNode = currentNode-> දකුණ
        • තාවකාලික-> හරි නම් නැත:
            • මෙම නෝඩය නූල් කරන්න temp-> right = currentNode
            • වම් උප කුලකය දැන් සකසන්න, currentNode = currentNode-> වමේ

මොරිස් ඉනෝඩර් ට්‍රැවර්සල් ක්‍රියාත්මක කිරීම

සී ++ වැඩසටහන

#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), සමහර විචල්‍යයන් ප්‍රකාශ කිරීම සඳහා අපි නියත අවකාශය භාවිතා කරන බැවින්. එහෙත්, වෙනත් අරමුණු සඳහා වෙනත් සහායක අවකාශයක් භාවිතා නොවේ. මොරිස් ඉනෝඩර් ට්‍රැවර්සල් පොරොන්දු වන්නේ එයයි.