မောရစ် Inorder ဖြတ်သန်း


ခက်ခဲအဆင့် အလယ်အလတ်
သစ်ပင် သစ်ပင်လှည့်လည်

သစ်ပင်တစ်ပင်ကိုဖြတ်သန်းနိုင်တယ် စနစ်တကျဖြစ်သည် အသုံးပြု။ ကြားမှာဖက်ရှင် စုပုံထားဒါပေမယ့်အာကာသကိုစားတယ်။ ဒီတော့ဒီပြproblemနာမှာ linear space ကိုအသုံးမပြုပဲသစ်ပင်တစ်ပင်ကိုဖြတ်သွားလိမ့်မယ်။ ဒီအယူအဆကို Morris Inorder Traversal or Binary သစ်ပင်တွေမှာ Threading လို့ခေါ်တယ်။

နမူနာ

          2

       /      \

     1           3

  /      \

4          5
4 1 5 2 3
       3

    /      \

  1          4
            
          /      \
 
        2          5
1 3 2 4 5

ချဉ်းကပ်နည်း

အယူအဆမှာ - အကယ်၍ ကျွန်ုပ်တို့သည် အကယ်၍ ကျွန်ုပ်တို့သည် အကယ်၍ ကျွန်ုပ်တို့သည်အပင်၏နေရာ (သို့မဟုတ်ပြန်လည်အသုံးချနိုင်သောအရန်နေရာ) မပါဘဲသစ်ပင်ကိုဖြတ်သန်းနိုင်သည် မည်သည့်ဆုံမှတ်၏လိပ်စာကိုမဆုံးရှုံးပါစေနှင့် ငါတို့မှတ်ဉာဏ်ထဲမှာမသိမ်းဆည်းဘဲအစောပိုင်းကသွားရောက်ခဲ့သည်။ ဒီချဉ်းကပ်မှုဟုခေါ်သည် မောရစ် Inorder ဖြတ်သန်း.

သို့သော်မည်သည့်နေရာမှခွင့်မပြုပါက node များ၏လိပ်စာများကိုမည်သို့သိုလှောင်နိုင်မည်နည်း။ အယူအဆမှာသစ်ပင်၏ဖွဲ့စည်းပုံကိုဤသို့သောနည်းလမ်းဖြင့်ပြောင်းလဲရန်ဖြစ်သည်။ root node မှ subtree တစ်ခုမှအချို့သောအထူး node များသို့လည်ပတ်ပြီးနောက်၎င်းသည်အခြား subtree ကိုလုပ်ဆောင်ရန် root node သို့ပြန်သွားနိုင်သည်။ ဘယ်ဘက် subtree ကိုအပြည့်အ ၀ လည်ပတ်ခဲ့ပြီး၊ ဘယ် subtree ၏အချို့ node တစ်ခုမှ pointer ထပ်ထပ်ထည့်ပါ။ ယခုကျွန်ုပ်တို့သည်မူလအမြစ်သို့ပြန်သွားခြင်းဖြင့်မှန်ကန်သော subtree ကိုလုပ်ဆောင်နိုင်သည်။ Morris Inorder Traversal တွင်အမြစ်တစ်ခု၏အတွင်းပိုင်း (၎င်း၏လက်ဝဲ subtree ၌) ကိုသူ့ဟာသူချိတ်ဆက်ပေးသည်။

မောရစ် Inorder ဖြတ်သန်းမှုကို C ++ သင်ခန်းစာ

ထောက်ပြသည့်ဤလုပ်ငန်းစဉ် (ချည်) inorder ရှေ့ကနေ root အထိခေါ်တယ် ချည်။ တနည်းကား၊ သစ်ပင်၏ဖွဲ့စည်းပုံကိုကျွန်ုပ်တို့မနှောင့်ယှက်ချင်သောကြောင့်ကျွန်ုပ်တို့သည်လင့်များနှင့်အလိုအလျောက်ဖျက်ပစ်မည့် algorithm ကိုဒီဇိုင်းဆွဲပါမည် မုန်းတီးမှု သစ်ပင်ကြီး ၎င်း၏မူလဖွဲ့စည်းပုံကိုဆက်လက်ထိန်းသိမ်းရန်.

algorithm

  1. လက်ရှိ node ကိုသစ်ပင်၏အမြစ်အဖြစ်စတင်ပါ။
  2. ကျနော်တို့ဘယ်မှာရှိအခြေအနေသို့ရောက်ရှိမှီတိုင်အောင် iterating ထားပါ လက်ရှိ node ကို ဖြစ်လာ null ။ 
    • အလိုလျှင် လက်ဝဲဘက် လက်ရှိအမြစ်၏ subtree ဖြစ်ပါတယ် null :
        • ယခုကျွန်ုပ်တို့သည် root ကို print ထုတ်ပြီးညာဘက် subtree သို့ရွှေ့နိုင်သည်။ ထို့ကြောင့် currentNode = currentNode-> right ။
    • အလိုလျှင် လက်ဝဲဘက် လက်ရှိအမြစ်၏ subtree ဖြစ်ပါတယ်  null :
        • ဤကိစ္စတွင်ကျွန်ုပ်တို့သည် unthread / ချည် သူ့ဟာသူမှလက်ရှိ node ကို၏လက်ဝဲ subtree (inorder ယခင်) အတွက် rightmost node ကို
            • အပူချိန် = currentNode-> left;
            • စဉ် temp-> ညာဘက်ဖြစ်ပါတယ် null သို့မဟုတ်အပူသည် NOT currentNode
              • အပူချိန် = temp-> ညာဘက်
        • temp-> မှန်လျှင် null:
            • အဖြစ် threading ဖယ်ရှားလိုက်ပါ temp-> ညာဘက် = null
            • လက်ျာ subtree, currentNode = currentNode-> ညာဘက်ကို process
        • temp-> မှန်လျှင် NULL မဟုတ် -
            • အဖြစ်ဒီ node ကိုချည် temp-> ညာဘက် = currentNode
            • လက်ဝဲ subtree ကိုယခု process, currentNode = currentNode-> left

မောရစ် Inorder ဖြတ်သန်း၏အကောင်အထည်ဖော်မှု

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

မောရစ် Inorder ဖြတ်သန်း၏ရှုပ်ထွေးအားသုံးသပ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N)၊ N သည်သစ်ပင်ရှိ node များ၏နံပါတ်ဖြစ်သည်။ node တိုင်းကို ၂ ကြိမ်အတိအကျလည်ပတ်ကြောင်းသေချာသည်။ ထိုသူအားလုံးသည် threading နှင့် unthreading လုပ်ငန်းစဉ်ကိုဖြတ်သန်းသွားသောအခါဖြစ်သည်။ ဒါပေမယ့်အချိန်ရှုပ်ထွေး linear နေဆဲဖြစ်သည်။

အာကာသရှုပ်ထွေးမှု

အို (၁)၊ ကျွန်တော်အချို့ variable တွေကိုကြေငြာဘို့စဉ်ဆက်မပြတ်အာကာသကိုသုံးပါအဖြစ်။ သို့သော်မည်သည့်အခြားအရန်နေရာမျှမရည်ရွယ်ပါ။ Morris Inorder Traversal ကထိုအရာကိုကတိပေးသည်။