Обръщане на Morris Inorder


Ниво на трудност M
Дърво Обръщане на дърво

Можем да прекосим дърво в Inorder мода итеративно, използвайки купчина, но отнема пространство. И така, в този проблем ще преминем през дърво, без да се използва линейното пространство. Тази концепция се нарича Morris Inorder Traversal или Threading in Binary trees.

Пример

          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 ние свързваме предшественика inorder на корен (в лявото му поддърво) със себе си.

Morris Inorder Traversal C ++ Урок

Този процес на добавяне на указатели (теми) от inorder предшественик до root се извиква резбоване. Отново не искаме да нарушаваме структурата на дървото, затова ще проектираме алгоритъм, който автоматично изтрива връзките и неконци дървото до запазват първоначалната си структура.

алгоритъм

  1. Инициализирайте текущия възел като корен на дървото.
  2. Продължавайте да повтаряте, докато достигнем състоянието, където текущ възел става НУЛА. 
    • Ако наляво поддърво на текущия корен е NULL :
        • Вече можем да отпечатаме корена и да се преместим в дясното поддърво, така че currentNode = currentNode-> вдясно.
    • Ако наляво поддърво на текущия корен е  НЕ NULL :
        • В този случай ние неконци / нишка най-десния възел в лявото поддърво (inorder предшественик) на текущия възел към себе си
            • temp = currentNode-> ляво;
            • Докато temp-> правото е НЕ NULL или temp е НЕ текущ възел
              • temp = temp-> вдясно
        • Ако temp-> right е NULL:
            • премахване на резбата като temp-> вдясно = NULL
            • обработва дясното поддърво, currentNode = currentNode-> right
        • Ако temp-> right е НЕ НУЛО:
            • нишка този възел като temp-> вдясно = currentNode
            • Обработете лявото поддърво сега, currentNode = currentNode-> left

Прилагане на 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 е броят на възлите в дървото. Сигурно е, че посещаваме всеки възел точно 2 пъти, тъй като всички те преминават през процеса на резбоване и освобождаване на резби. Но сложността във времето остава линейна.

Сложност на пространството

O (1), тъй като използваме постоянно пространство за деклариране на някои променливи. Но, друго спомагателно пространство не се използва за каквато и да е цел. За това обещава Morris Inorder Traversal.