Morris Inorder Traversal


Դժվարության մակարդակ Միջին
ծառ Reeառի անցում

Մենք կարող ենք ծառի միջով անցնել որպեսզի նորաձեւություն կրկնվող ՝ օգտագործելով բուրգ, բայց դա սպառում է տարածքը: Այսպիսով, այս խնդրում մենք պատրաստվում ենք ծառ ծառահատել առանց գծային տարածության օգտագործման: Այս գաղափարը կոչվում է 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 Traversal.

Բայց առանց որևէ թույլատրելի տարածության, ինչպե՞ս կարելի է պահպանել հանգույցների հասցեները: Գաղափարն այն է, որ ծառի կառուցվածքը փոխվի այնպես, որ արմատային հանգույցից մեկ ենթաընտանի որոշ հատուկ հանգույցներ այցելելուց հետո մենք կարողանանք վերադառնալ արմատային հանգույց ՝ մշակելու դրա մյուս ենթա ծառը: Ասենք, որ մենք ամբողջությամբ այցելել ենք ձախ ենթտառ, և ձախ ենթածառի որոշ հանգույցներից ցուցիչ կրկին ավելացրինք արմատին: Այժմ մենք կարող ենք վերամշակել ճիշտ ենթատեսակը ՝ վերադառնալով բուն արմատին: Morris Inorder Traversal- ում մենք կապում ենք արմատից առաջացող նախորդ կարգի նախորդը (իր ձախ ենթածառի մեջ) ինքն իրեն:

Morris Inorder Traversal C ++ ձեռնարկը

Pointուցանակներ ավելացնելու այս գործընթացը (Թեմաներ) նախորդ նախորդից արմատից կոչվում է թելը Կրկին, մենք չենք ուզում խանգարել ծառի կառուցվածքը, այնպես որ մենք կմշակենք ալգորիթմ, որն ավտոմատ կերպով ջնջում է հղումները և անթելեր ծառը դեպի պահպանել իր նախնական կառուցվածքը.

Ալգորիթմ

  1. Նախնականացնել ընթացիկ հանգույցը որպես ծառի արմատ:
  2. Շարունակեք կրկնվել, մինչև հասնենք այն պայմանին, երբ ընթացիկ հանգույց դառնում ԴԱՏԱՐԿ. 
    • Եթե դուրս Ընթացիկ արմատի ենթատետրն է NULL, :
        • Այժմ մենք կարող ենք տպել արմատը և շարժվել դեպի աջ ենթատեսակ, այնպես որ currentNode = currentNode-> աջ:
    • Եթե դուրս Ընթացիկ արմատի ենթատետրն է  ՈՉ NULL, :
        • Այս դեպքում մենք անթել / թել ընթացիկ հանգույցի ձախ մասի ձախ ենթածառի աջ անկյունը (նախորդ նախորդը)
            • temp = ընթացիկՆոդ-> ձախ;
            • Ժամանակ տեմպ-> ճիշտ է ՈՉ NULL, կամ ժամանակավոր է ՉԻ ընթացիկ հանգույց
              • temp = temp-> ճիշտ է
        • Եթե ​​temp-> ճիշտ է NULL,:
            • հեռացնել թելերը, ինչպես temp-> աջ = NULL
            • մշակել ճիշտ ենթածառը, ընթացիկՆոդ = ընթացիկՆոդ-> ճիշտ
        • Եթե ​​temp-> ճիշտ է ՉԻ ULՈՒԼ
            • թեմա այս հանգույցը, ինչպես temp-> աջ = ընթացիկ հանգույց
            • Այժմ մշակեք ձախ ենթածառը, ընթացիկՆոդ = ընթացիկՆոդ-> ձախ

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- ի բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ), որտեղ N- ը ծառի հանգույցների քանակն է: Հաստատ է, որ յուրաքանչյուր հանգույց մենք այցելում ենք ուղիղ 2 անգամ, քանի որ բոլորն անցնում են թելելու և չթելադրելու գործընթաց: ,Ամանակի բարդությունը մնում է գծային:

Տիեզերական բարդություն

O (1), քանի որ մենք օգտագործում ենք անընդհատ տարածություն որոշ փոփոխականների հայտարարման համար: Բայց ոչ մի այլ օժանդակ տարածք չի օգտագործվում որևէ նպատակով: Ահա թե ինչի մասին է խոստանում Morris Inorder Traversal- ը: