מאָריס ינאָרדער טראַווערסאַל


שוועריקייט לעוועל מיטל
בוים בוים טראַווערסאַל

מיר קענען אַריבער אַ בוים אין די אין איינקלאנג מאָדע יטעראַטיוולי, ניצן stack, אָבער עס קאַנסומז פּלאַץ. אין דעם פּראָבלעם, מיר וועלן אַריבער אַ בוים אָן די לינעאַר פּלאַץ איז געניצט. דער באַגריף איז גערופֿן מאָריס ינאָרדער טראַווערסאַל אָדער טרעדינג אין ביינערי ביימער.

בייַשפּיל

          2

       /      \

     1           3

  /      \

4          5
4 1 5 2 3
       3

    /      \

  1          4
            
          /      \
 
        2          5
1 3 2 4 5

צוגאַנג

דער געדאַנק איז: מיר קענען אַריבער דעם בוים אָן די פּלאַץ פון אַ אָנלייגן (אָדער די הילף פּלאַץ פון רעקורסיאָן) אויב מיר טאָן ניט פאַרלירן די אַדרעס פון קיין נאָדע מיר באזוכט פריער אָן סטאָרינג זיי אין דער זכּרון. דעם צוגאַנג איז גערופן מאָריס ינאָרדער טראַווערסאַל.

ווי אַזוי קען מען קראָם די אַדרעסעס פון נאָודז אָן קיין פּלאַץ ערלויבט? דער געדאַנק איז צו טוישן די סטרוקטור פון דעם בוים אַזוי אַז נאָך באזוכן עטלעכע נאָודז פון איין סובטרעע פֿון דער וואָרצל נאָדע, מיר קענען צוריקקומען צו די וואָרצל נאָדע צו פּראָצעס זיין אנדערע סובטרעע. זאָגן מיר האָבן גאָר באזוכט די לינקס סובטרעע און לייגן ווידער אַ טייַטל פֿון עטלעכע לינקס צו די וואָרצל. איצט, מיר קענען פּראָצעס די רעכט סובטרעע דורך צוריקקומען צו דער אָריגינעל וואָרצל. אין Morris Inorder Traversal, מיר פֿאַרבינדן די ינאָרדער פאָרויסגייער פון אַ וואָרצל (אין זיין לינקס סאַבסטרי) צו זיך.

מאָריס ינאָרדער טראַווערסאַל C ++ טוטאָריאַל

דער פּראָצעס פון אַדינג פּוינטערז (פֿעדעם) פֿון די ינאָרדער פאָרויסגייער צו וואָרצל איז גערופֿן טרעדינג. ווידער, מיר טאָן נישט וועלן צו שטערן דעם בוים, אַזוי מיר וועלן אָנצייכענען אַ אַלגערידאַם אַז אויטאָמאַטיש דיליץ די לינקס און ונטהרעאַדס דער בוים צו ריטיין זייַן אָריגינעל סטרוקטור.

אַלגאָריטהם

  1. יניטיאַליזירן דעם קראַנט נאָדע ווי וואָרצל פון דעם בוים.
  2. האַלטן יטעראַטינג ביז מיר דערגרייכן די צושטאַנד ווו די קראַנט נאָדע ווערט נול. 
    • אויב די לינקס סובטרעע פון ​​דעם קראַנט שורש איז נאַל :
        • מיר קענען איצט דרוקן די וואָרצל און מאַך צו די רעכט סובטרעע, אַזוי קראַנטNode = קראַנט נאָדע-> רעכט.
    • אויב די לינקס סובטרעע פון ​​דעם קראַנט שורש איז  נישט נאַל :
        • אין דעם פאַל, מיר ונטהרעאַד / פאָדעם די רעכט רעכט נאָדע אין די לינקס סובטרעע (ינאָרדער פאָרויסגייער) פון די קראַנט נאָדע צו זיך
            • טעמפּ = קראַנט נאָדע-> לינקס;
            • ווייַלע טעמפּ-> רעכט איז נישט נאַל אָדער טעמפּ איז נישט איצטיקע נאָדע
              • טעמפּ = טעמפּ-> רעכט
        • אויב טעמפּ-> רעכט איז נאַל:
            • אַראָפּנעמען טרעדינג ווי טעמפּ-> רעכט = נול
            • פּראָצעס די רעכט סובטרעע, קראַנטנאָדע = קראַנט נאָדע-> רעכט
        • אויב טעמפּ-> רעכט איז נישט נול:
            • פֿאָדעם דעם נאָדע ווי טעמפּ-> רעכט = קראַנט נאָדע
            • פּראַסעס די לינקס סובטרעע איצט, קראַנטנאָדע = קראַנטנאָדע-> לינקס

ימפּלעמענטאַטיאָן פון Morris Inorder Traversal

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

Java פּראָגראַם

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

קאַמפּלעקסיטי אַנאַליסיס פון Morris Inorder Traversal

צייט קאַמפּלעקסיטי

אָ (N), וווּ N איז די נומער פון נאָודז אין דעם בוים. עס איז זיכער אַז מיר באַזוכן יעדער נאָדע פּונקט 2 מאָל, ווייַל זיי אַלע דורכגיין דעם פּראָצעס פון טרעדינג און ונטהרעאַדינג. אָבער די צייט קאַמפּלעקסיטי בלייבט לינעאַר.

ספעיס קאַמפּלעקסיטי

אָ (1), ווי מיר נוצן קעסיידערדיק פּלאַץ פֿאַר דיקלערינג עטלעכע וועריאַבאַלז. אָבער, קיין אנדערע אַגזיליערי פּלאַץ איז געניצט פֿאַר קיין ציל. דאָס איז וואָס Morris Inorder Traversal הבטחות וועגן.