موریس د داخلي سفرونه


مشکل کچه منځني
ونې د ونې تراشل

موږ کولی شو په یوه کې ونې تېر کړو منظم فیشن په تکراري ډول ، په کارولو سره ډک، مګر دا ځای مصرفوي. نو ، پدې ستونزه کې ، موږ د ونې تیریدو پرته د خطي ځای کارولو پرته. دا مفهوم د موریس انډر ټریورسال یا په بائنري ونو کې تیوري ویل کیږي.

بېلګه

          2

       /      \

     1           3

  /      \

4          5
4 1 5 2 3
       3

    /      \

  1          4
            
          /      \
 
        2          5
1 3 2 4 5

او کړنلاره

نظر دا دی: موږ کولی شو ونه د کڅوړې ځای پرته (یا د مرستندویه کولو معاون ځای) پرته وګرځوو که چیرې موږ د هیڅ نوډ پته له لاسه مه ورکوئ موږ دمخه لیدنه کړې پرته له دې چې دوی یې په حافظه کې زیرمه کړو. دې چلند ته ویل کیږي موریس د داخلي سفرونه.

مګر پرته د کوم ځای اجازه ورکړل شوي ، یو څوک څنګه د نوډونو پتې ذخیره کولی شي؟ نظر دا دی چې د ونې جوړښت پدې ډول بدل کړي ، دا چې د ریښې نوډ څخه د یوې فرعي ونې ځینې ځانګړي نوډونو لیدلو وروسته ، موږ کولی شو د دې نورې فرعي پروسس کولو لپاره بیرته د ریښې نوډ ته ورشو. ووایاست چې موږ په بشپړه توګه کی visited اړخ ته لیدنه کړې ، او بیا د کی subې فرعي ژبې د ځینې نوډ څخه یو نښې بیا ریښې ته اضافه کوو. اوس ، موږ کولی شو اصلي ریښې ته د بیرته راستنیدو سره سم فرعي عمل پروسس کړو. په موریس انډر ټریورسال کې ، موږ د انارډ مخکیني پیشو ته د یوې ریښې (په کی its اړخ کې) خپل ځان سره نښلولو.

موریس انډر ټریورسل سي ++ ټیوټوریل

د نښو اضافو کولو پروسه (سلسلې) د انډر پیشرو څخه تر ریښي ته ویل کیږي تار ورکول. یوځل بیا ، موږ نه غواړو د ونې جوړښت ګډوډ کړو ، نو موږ به یو الگوریتم ډیزاین کړو چې اتومات لینکونه حذف او بې خطره ونې ته خپل اصلي جوړښت وساتئ.

الګوریتم

  1. اوسنی نوډ د ونې د ریښې په توګه پیل کړئ.
  2. تکرارولو ته دوام ورکوو تر هغه چې حالت ته ورسیږو چیرې چې اوسنی نوډ شي شمال. 
    • که پاتې د اوسني ریښې فرعي دی مردود :
        • موږ اوس کولی شو ریښه چاپ کړو او ښۍ فرعي ته لاړ شو ، نو له همدې امله کرینټینډ = کرینټ نوډ-> ښیې.
    • که پاتې د اوسني ریښې فرعي دی  نه مردود :
        • پدې حالت کې ، موږ بې خطره / تار ځان ته د اوسني نوډ کی left اړخ فرعي برخه (د انډول پیشګویی) ښي لاس نوډ
            • عارضي = اوسني نوډ-> پاتې؛
            • په داسې حال کې temp-> سمه ده نه مردود یا عارضي دی اوسنی نوم نه
              • عارضي = لنډ-> سم
        • که لنډ-> سم دی مردود:
            • څرنګوالې لرې کړئ لکه temp-> حق = NULL
            • ښۍ ضمني پروسه، اوسني نوم = اوسنی نوم-> ښیې
        • که لنډ-> سم دی نه
            • دا نوډ لکه څرنګه لنډ-> حق = اوسنی نوډ
            • اوس کی sub برخې ته پروسه وکړئ ، اوسنی نوم = اوسنی نوم-> کی.

د موريس داخلي تګ راتګ پلي کول

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 (1) ، لکه څنګه چې موږ د ځینې تغیراتو څرګندولو لپاره ثابت ځای کار کوو. مګر ، د کوم بل معاون ځای د کوم هدف لپاره ندي کارول کیږي. دا هغه څه دي چې د موريس انډر ټریورسل ژمنې کوي.