ကြားမှာ Preorder ဖြတ်သန်း


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် အမေဇုံ Google JP Morgan Microsoft က မော်ဂန်စတန်လေ Uber
သစ်ပင် သစ်ပင်လှည့်လည်

“ Iterative Preorder Traversal” ပြproblemနာကသင့်အား binary tree ပေးပြီးယခုရှာဖွေရန်လိုအပ်သည်ဟုဖော်ပြသည် preorder ဖြတ်သန်း သစ်ပင်၏။ ကျွန်ုပ်တို့သည်ကြိုတင်ဖြတ်သန်းမှုလမ်းကြောင်းကိုထပ်တလဲလဲအသုံးပြုခြင်းနည်းလမ်းဖြင့်အသုံးပြုခြင်းကိုရှာဖွေရန်လိုအပ်သည်။

နမူနာ

ကြားမှာ Preorder ဖြတ်သန်း

 

5 7 9 6 1 4 3

ပုံနှိပ်ဖို့ချဉ်းကပ်

အဆိုပါပြstatementနာကြေညာချက် iterative နည်းလမ်းကိုအသုံးပြု။ ပေးထားသော binary သစ်ပင်၏ preorder ဖြတ်သန်းပုံနှိပ်ဖို့ကျွန်တော်တို့ကိုမေးတယ်။ ယေဘုယျအားဖြင့်တော့ကျနော်တို့က recursive method ကိုသုံးတယ်။ သို့သော်တစ်ခါတစ်ရံပြtheနာကို အသုံးပြု၍ ပြtheနာကိုဖြေရှင်းရန်တောင်းဆိုသည်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည်သစ်ပင်၏ကြားဖြတ်ကြိုတင်မှာယူမှုဖြတ်သန်းရန်ဤနေရာတွင်လိုအပ်သည်။

ယခင်ကငါတို့သုံးခဲ့သည် ပြန်လည် အဆိုပါဖြတ်သန်းပုံနှိပ်ရန်။ ဒီတော့ recursion ကိုအစားထိုးဖို့၊ စုပုံထား ဒေတာဖွဲ့စည်းပုံ။ ဒီတော့နောက်မှလိုအပ်မည့် node များကိုသိမ်းရန် stack data structure ကိုအသုံးပြုလိမ့်မည်။ preorder traversal တွင်၊ ကျွန်ုပ်တို့သည် root ကို print ထုတ်ပြီးဘယ်ဘက် subtree ကိုပြန်လည်ထုတ်ယူသည်။ ဤ algorithm တွင်ကျွန်ုပ်တို့သည်လက်ရှိ node သည် null မဟုတ်သည့်တိုင်အောင် run လိမ့်မည်။ ပြီးတော့မှန်ကန်တဲ့ကလေးရှိရင်လက်ျာကလေးကိုဆက်ပြီးသိမ်းထားမှာပါ။ ပြီးရင်လက်ဝဲကလေးဆီကိုသွားမယ်။ ဘယ်ဘက်ကလေးသည် null ဖြစ်ပါကကျွန်ုပ်တို့သည် element များကို stack မှဖယ်ထုတ်ပြီး၎င်းတို့ကိုလက်ရှိ node အဖြစ်သတ်မှတ်သည်။ ဤနည်းဖြင့်ကျွန်ုပ်တို့သည်သစ်ပင်ကိုကြိုတင်မှာယူပြီးဖြတ်ကျော်သွားလိမ့်မည်။

ကုဒ်

Iterative Preorder Traversal ကို print ထုတ်ရန် C ++ ကုဒ်

#include<bits/stdc++.h>
using namespace std;

struct node {
  int data;
  node *left, *right;
};

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->left = tmp->right = NULL;
  return tmp;
}

void preorder(node* root){
    // create a stack
    stack<node*> s;

    while(root){
        // print the current node
        cout<<root->data<<" ";
        
        // if current node has right sub-tree
        // then store it and use it afterwards
        if(root->right)
            s.push(root->right);
        // now move to left child of current node
        // if the left child does not exists 
        // then in the next condition we will move up in the tree
        // and assign the right children which 
        // we have been storing the stack
        root = root->left;
        if(!root && !s.empty()){
                root = s.top(), s.pop();
        }
    }
}

int main()
{
  node* root = create(5);
  root->left = create(7);
  root->right = create(3);
  root->left->left = create(9);
  root->left->right = create(6);
  root->left->right->left = create(1);
  root->left->right->right = create(4);

  preorder(root);
}
5 7 9 6 1 4 3

Iterative Preorder Traversal ကို print ထုတ်ရန် Java code

import java.util.*;

class node{
  int data;
  node left, right;
}

class Main{

  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = tmp.right = null;
    return tmp;
  }

  static void preorder(node root){
      // create a stack
      Stack<node> s = new Stack<node>();

      while(root != null){
          // print the current node
          System.out.print(root.data+" ");

          // if current node has right sub-tree
          // then store it and use it afterwards
          if(root.right != null)
              s.add(root.right);
          // now move to left child of current node
          // if the left child does not exists
          // then in the next condition we will move up in the tree
          // and assign the right children which
          // we have been storing the stack
          root = root.left;
          if(root == null && !s.empty()){
                  root = s.peek();
                  s.pop();
          }
      }
  }

  public static void main(String[] args)
  {
    node root = create(5);
    root.left = create(7);
    root.right = create(3);
    root.left.left = create(9);
    root.left.right = create(6);
    root.left.right.left = create(1);
    root.left.right.right = create(4);

    preorder(root);
  }
}
5 7 9 6 1 4 3

ရှုပ်ထွေးဆန်းစစ်ခြင်း

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

အို (N)၊ ကျနော်တို့သစ်ပင်အပေါငျးတို့သ element တွေကိုဖြတ်သန်းကတည်းက။ ထို့ကြောင့်အချိန်ရှုပ်ထွေးမှုမှာ linear ဖြစ်သည်။

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

အို (H)၊ အဆိုးဆုံးအနေဖြင့် node တစ်ခုစီသည်မှန်ကန်သောကလေးရှိနိုင်သည်။ ဘာလို့လဲဆိုတော့ကျွန်တော်တို့ဟာဘယ်ဘက်ကလေးဆီသို့လမ်းကြောင်းတစ်လျှောက်ရှိ node တစ်ခုစီ၏မှန်ကန်သောကလေးကိုသိုလှောင်ထားခြင်းကြောင့်ဖြစ်သည်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည် max O (H) node များထဲတွင် stack ထဲတွင်သိမ်းနိုင်သည်။