پیمایش Morris Inorder


سطح دشواری متوسط
درخت عبور از درخت

ما می توانیم از درختی در آن عبور کنیم به ترتیب مد بصورت تکراری ، با استفاده از پشته، اما باعث مصرف فضا می شود. بنابراین ، در این مشکل ، ما می خواهیم یک درخت را بدون استفاده از فضای خطی عبور دهیم. این مفهوم Morris Inorder Traversal یا Threading در درختان باینری نامیده می شود.

مثال

          2

       /      \

     1           3

  /      \

4          5
4 1 5 2 3
       3

    /      \

  1          4
            
          /      \
 
        2          5
1 3 2 4 5

روش

ایده این است: اگر ما بتوانیم درخت را بدون فضای پشته (یا فضای کمکی بازگشت) پیمایش کنیم آدرس هیچ گره ای را از دست ندهید ما قبلا بازدید کردیم بدون اینکه آنها را در حافظه ذخیره کنیم. این رویکرد نامیده می شود پیمایش Morris Inorder.

اما بدون وجود فضای خالی ، چگونه می توان آدرس گره ها را ذخیره کرد؟ ایده این است که ساختار درخت را به گونه ای تغییر دهیم که پس از بازدید از برخی گره های خاص یک زیر درخت از گره ریشه ، بتوانیم دوباره به گره ریشه برگردیم تا زیر درخت دیگر آن را پردازش کنیم. بگویید ما کاملا از درخت فرعی سمت چپ بازدید کرده ایم و یک نشانگر را از برخی گره های زیر درخت سمت چپ دوباره به ریشه اضافه کنید. اکنون ، ما می توانیم با بازگشت به ریشه اصلی ، زیر درخت مناسب را پردازش کنیم. در Morris Inorder Traversal ، ما پیشینی غیرorder یک ریشه (در زیر شاخه سمت چپ آن) را به خود پیوند می دهیم.

آموزش Morris Inorder Traversal C ++

این روند اضافه کردن اشاره گرها (موضوعات) از سلف inorder به root گفته می شود نخ کشیدن باز هم ، ما نمی خواهیم ساختار درخت را بهم بزنیم ، بنابراین الگوریتمی طراحی خواهیم کرد که به طور خودکار پیوندها را حذف کند و بدون نخ ها درخت به ساختار اصلی خود را حفظ کند.

الگوریتم

  1. گره فعلی را به عنوان ریشه درخت شروع کنید.
  2. تکرار کنید تا زمانی که به شرایطی برسیم که گره فعلی شود خالی. 
    • اگر ترک کرد subtree از ریشه فعلی است NULL :
        • اکنون می توانیم ریشه را چاپ کرده و به زیر درخت سمت راست برویم ، بنابراین currentNode = currentNode-> سمت راست.
    • اگر ترک کرد subtree از ریشه فعلی است  نه NULL :
        • در این حالت ، ما نخ نخ / نخ گره سمت راست در زیر شاخه سمت چپ (ترتیب قبلی) گره فعلی به خودش
            • temp = currentNode-> سمت چپ؛
            • در حالی که temp-> درست است نه NULL یا دما است NOTNode نیست
              • temp = temp-> درست است
        • اگر temp-> درست است NULL:
            • حذف رشته به عنوان temp-> right = NULL
            • زیر درخت راست را پردازش کنید ، currentNode = currentNode-> درست است
        • اگر temp-> درست است تهی نیست:
            • این گره را به عنوان رشته کنید temp-> right = currentNode
            • زیر درخت چپ را اکنون پردازش کنید ، currentNode = 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

تجزیه و تحلیل پیچیدگی پیمایش ناهماهنگ موریس

پیچیدگی زمان

بر)، جایی که N تعداد گره های درخت است. مطمئناً ما دقیقاً 2 بار از هر گره بازدید می کنیم ، زیرا همه آنها روند نخ و نخ نخ گرفتن را طی می کنند. اما ، پیچیدگی زمان همچنان خطی است.

پیچیدگی فضا

O (1) ، همانطور که برای اعلام برخی از متغیرها از فضای ثابت استفاده می کنیم. اما ، هیچ فضای کمکی دیگری برای هر منظور استفاده نمی شود. این همان چیزی است که Morris Inorder Traversal در مورد آن قول می دهد.