ကြိုတင်မှာယူမှုဖြတ်သန်းရာမှ BST ၏ postorder ဖြတ်သန်းရှာဖွေပါ


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် အမေဇုံ လေးကစ် PayU
Binary Search Tree သစ်ပင်လှည့်လည်

ပြProbleနာဖော်ပြချက်

“ Border ၏ postorder ဖြတ်သန်းမှုကိုကြိုတင်ဖြတ်သန်းခြင်းမှရှာဖွေခြင်း” ပြproblemနာကသင်က binary search tree ၏ကြိုတင်မှာယူခြင်းကိုပေးသည်ဟုဖော်ပြသည်။ ထို့နောက်ပေးထားသော input ကိုအသုံးပြု။ postorder ဖြတ်သန်းရှာပါ။

နမူနာ

ကြိုတင်မှာယူမှုဖြတ်သန်းရာမှ BST ၏ postorder ဖြတ်သန်းရှာဖွေပါ

preorder traversal sequence: 5 2 1 3 4 7 6 8 9
1 4 3 2 6 9 8 7 5

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

ပေးထားသောပြproblemနာကကျွန်တော်တို့ဟာ binary search tree ၏ကြိုတင်မှာယူသောလမ်းကြောင်းလမ်းကြောင်းကိုပေးသည်ဟုဆိုသည်။ ယခုကျွန်ုပ်တို့သည်သစ်ပင်၏ postorder ဖြတ်သန်းမှုကိုထည့်သွင်းရန်လိုအပ်ပြီး input နှင့်ထပ်တူ preorder ဖြတ်သန်းမှုကိုတွေ့ရှိရန်လိုအပ်သည်။ ဤပြproblemနာကိုထိထိရောက်ရောက်ဖြေရှင်းရန်ကျွန်ုပ်တို့လိုအပ်သည်။

နုံတဲ့ချဉ်းကပ်နည်းကိုအရင်သုံးပါ ကြိုတင်အော်ဒါမှာယူသည် ဖြတ်သန်းနှင့်တည်ဆောက် BST။ ထို့နောက်အသစ်တည်ဆောက်ထားသောသစ်ပင်ပေါ်တွင် postorder ဖြတ်ကူးခြင်းကိုရိုးရှင်းစွာလုပ်ပါ။ သို့သော်ဤချဉ်းကပ်မှုသည်နေရာနှင့် ပတ်သက်၍ ထိရောက်မှုမရှိပါ။ အဘယ်ကြောင့်ဆိုသော်ဆောက်လုပ်ထားသောသစ်ပင်သည် overhead တစ်ခုအနေဖြင့်လုပ်ဆောင်ခြင်းကြောင့်ဖြစ်သည်။

ပြtheနာကိုထိထိရောက်ရောက်ဖြေရှင်းနိုင်ဖို့အတွက်ကျနော်တို့ input array ကိုဖြတ်သန်းပါတယ်။ အဆိုပါ input ကိုခင်းကျင်းကျွန်တော်တို့ရဲ့ preorder ဖြတ်သန်းသည်။ ဒါကြောင့်ကျနော်တို့ preorder ဖြတ်သန်းသွား။ လက်ရှိဒြပ်စင်မုသာမသုံးသင့်ရှိမရှိရှာပါ။ ပထမဆုံး element ကိုစတင်သောအခါကျွန်ုပ်တို့သည်အနည်းဆုံး integer တန်ဖိုးမှအများဆုံး integer တန်ဖိုးသို့သတ်မှတ်သည်။ ဘာဖြစ်လို့လဲဆိုတော့ preorder traversal ဟာဘယ်ဘက်နဲ့ညာ subtree မတိုင်ခင်မှာ root ရှိတယ်။ ဘယ်ဘက် subtree တည်ရှိပါက element များသည်နိမ့်ကျသောကိန်းဂဏန်းမှအမြစ်ထက်နည်းသောတန်ဖိုးသို့ရောက်သင့်ကြောင်းကျွန်ုပ်တို့သိသည်။ အလားတူပင်ပိုမိုကြီးမားသောအမြစ်၏တန်ဖိုးမှအမြင့်ဆုံးကိန်းဂဏန်းတန်ဖိုးသို့လှဲသင့်ကြောင်းလက်ျာ subtree များအတွက်။ လက်ရှိဒြပ်စင်ကဒီအကွာအဝေး၌မတည်လျှင်။ ထို့နောက်၎င်းသည်အခြား subtree တွင်တည်ရှိသင့်သည် (ဆိုလိုသည်မှာ၎င်းသည်လက်ဝဲ subtree သည်လက်ျာ subtree နှင့်အပြန်အလှန်တည်ရှိသင့်သည်ထက်၎င်းသည်လက်ဝဲ subtree အတွက်အကျုံးမ ၀ င်ပါက) ဖြစ်သည်။

ကုဒ်

ကြိုတင်မှာယူမှုဖြတ်သန်းထံမှ BST ၏ postorder ဖြတ်သန်းရှာတွေ့မှ C ++ ကုဒ်

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

void preToPost(int input[], int n, int mn, int mx, int& idx)
{
  // base case
  if (idx == n)
    return;
  // if current element does not belong to current subtree
  if (input[idx] < mn || input[idx] > mx) {
    return;
  }

  // store the value of root ro print after printing its subtrees
  int root = input[idx];
  idx++;

  // recursively solve for left and right subtree
  preToPost(input, n, mn, root, idx);
  preToPost(input, n, root, mx, idx);
  // print root
  cout<<root<<" ";
}

int main()
{
  int input[] = {5, 2, 1, 3, 4, 7, 6, 8, 9};
  int n = (sizeof input)/(sizeof input[0]);
  int idx = 0;
  	preToPost(input, n, INT_MIN, INT_MAX, idx);
}
1 4 3 2 6 9 8 7 5

preorder ဖြတ်သန်းရာမှ BST ၏ postorder ဖြတ်သန်းမှုကိုရှာဖွေရန် Java code

import java.util.*;

class Main{
  static int idx = 0;
  static void preToPost(int input[], int n, int mn, int mx)
  {
    // base case
    if (idx == n)
      return;
    // if current element does not belong to current subtree
    if (input[idx] < mn || input[idx] > mx) {
      return;
    }

    // store the value of root ro print after printing its subtrees
    int root = input[idx];
    idx++;

    // recursively solve for left and right subtree
    preToPost(input, n, mn, root);
    preToPost(input, n, root, mx);
    // print root
    System.out.print(root+" ");
  }

  public static void main(String[] args)
  {
    int input[] = {5, 2, 1, 3, 4, 7, 6, 8, 9};
    int n = input.length;
    	preToPost(input, n, Integer.MIN_VALUE, Integer.MAX_VALUE);
  }
}
1 4 3 2 6 9 8 7 5

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

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

အို (N)ဘာလို့လဲဆိုတော့ငါတို့ပေးထားတဲ့ခင်းကျင်းခြင်းတစ်ခုလုံးကိုဖြတ်ကျော်ရမယ်။

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

အို (N), ဘာဖြစ်လို့လဲဆိုတော့ recursive လုပ်ဆောင်ချက်များကိုများအတွက်အသုံးပြုလျက်ရှိသော compiler ကို stack ကြောင့်ဖြစ်သည်။