Morris Inorder Traversal

Çətinlik səviyyəsi Mühit
Ağac Ağacın keçidiBaxılıb 27

Bir ağacdan keçə bilərik nizam istifadə edərək iterativ olaraq moda qalaq, ancaq yer alır. Beləliklə, bu problemdə, xətti boşluq istifadə edilmədən bir ağacdan keçəcəyik. Bu konsepsiya Morris Inorder Traversal və ya İkili ağaclarda iplik adlanır.

misal

          2

       /      \

     1           3

  /      \

4          5
4 1 5 2 3
       3

    /      \

  1          4
            
          /      \
 
        2          5
1 3 2 4 5

Yanaşma

Fikir budur: əgər yığın boşluğu olmadan (və ya köməkçi rekursiya sahəsi) olmadan ağacdan keçə bilərik. heç bir düyünün ünvanını itirməyin yaddaşda saxlamadan əvvəllər ziyarət etdik. Bu yanaşma deyilir Morris Inorder Traversal.

Ancaq icazə verilən boşluq olmadan, qovşaqların ünvanlarını necə saxlamaq olar? Fikir ağacın quruluşunu elə bir şəkildə dəyişdirməkdir ki, kök düyünündən bir alt ağacın bəzi xüsusi qovşaqlarını ziyarət etdikdən sonra digər alt ağacını işləmək üçün kök düyününə qayıda bilərik. Sol alt ağacı tamamilə ziyarət etdiyimizi söyləyin və sol alt ağacın bəzi qovşaqlarından kökünə bir göstərici əlavə edin. İndi orijinal kökünə qayıdaraq düzgün alt ağacı işləyə bilərik. Morris Inorder Traversal-da, bir kökün inorder sələfini (sol alt ağacında) özünə bağlayırıq.

Morris Inorder Traversal C ++ DərsliyiPin

Bu göstəriciləri əlavə etmək prosesi (mövzuları) inorder sələfindən kökünə deyilir iplik. Yenə də ağacın quruluşunu pozmaq istəmirik, buna görə əlaqələri avtomatik olaraq silmək üçün bir alqoritm hazırlayacağıq və yivsiz ağac orijinal quruluşunu qorumaq.

Alqoritm

  1. Cari düyünü ağacın kökü kimi başladın.
  2. Vəziyyəti çatana qədər təkrarlamağa davam edin cari düyün olur SIFIR. 
    • Əgər Zaman cari kökün alt ağacıdır NULL :
        • İndi kökü yazdırıb sağ alt ağaca keçə bilərik, buna görə currentNode = currentNode-> right.
    • Əgər Zaman cari kökün alt ağacıdır  EDİLMƏDİ NULL :
        • Bu vəziyyətdə biz işlənməmiş / mövzu cari düyünün sol alt ağacındakı (əvvəlki sələf) ən sağ node özünə
            • temp = currentNode-> sol;
            • Isə temp-> doğru EDİLMƏDİ NULL və ya tempdir CariNode deyil
              • temp = temp-> sağ
        • Temp-> right olarsa NULL:
            • kimi ipliyi çıxarın temp-> right = NULL
            • sağ alt ağacı işləyin, currentNode = currentNode-> right
        • Temp-> right olarsa NULL DEYİL:
            • bu düyünü asmaq temp-> right = currentNode
            • İndi sol alt ağacı işləyin, currentNode = currentNode-> sol

Morris Inorder Traversalın həyata keçirilməsi

C ++ Proqramı

#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 Proqramı

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 Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (N), burada N ağacdakı qovşaq sayıdır. Hər bir düyünü tam 2 dəfə ziyarət etdiyimiz şübhəsizdir, çünki hamısı yiv açma və sökmə prosesindən keçir. Ancaq zamanın mürəkkəbliyi xətti olaraq qalır.

Kosmik Mürəkkəblik

O (1), bəzi dəyişənlərin elan edilməsi üçün sabit yerdən istifadə etdiyimiz üçün. Ancaq başqa bir köməkçi sahə heç bir məqsəd üçün istifadə edilmir. Morris Inorder Traversalın vəd etdiyi şey budur.

Translate »
1