binary သစ်ပင်၏နယ်နိမိတ်ဖြတ်သန်း  


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် တိကျသော အမေဇုံ ခရီးသွား Kritikal ဖြေရှင်းချက် Microsoft က မော်ဂန်စတန်လေ PayU Snapdeal
ဒွိသစ်ပင် သစ်ပင် သစ်ပင်လှည့်လည်

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

“ binary tree of Borderary Traversal” ပြနာကသင့်အား binary tree ပေးသည်ဟုဖော်ပြသည်။ ယခုသင်သည် a ၏နယ်နိမိတ်မြင်ကွင်းကို print ထုတ်ရန်လိုအပ်သည် ဒွိသစ်ပင်။ ဤနေရာတွင်နယ်နိမိတ်ဖြတ်သန်းခြင်းဆိုသည်မှာ node များအားလုံးကိုသစ်ပင်၏နယ်နိမိတ်အဖြစ်ပြသသည်ဟုဆိုလိုသည်။ node များကိုအပေါ်ဘက်၊ ဘယ်ဘက်၊ အောက်ဘက်နှင့်ညာဘက်ခြမ်းတို့မှနာရီလက်တံဆန့်ကျင်သောလမ်းကြောင်းမှမြင်ရသည်။ သို့သော်ကျွန်ုပ်တို့သည်ဤအမြင်များအားလုံးကိုတိုက်ရိုက်ပုံနှိပ်ထုတ်ဝေလျှင်၎င်းသည်တူညီသော node များအကြိမ်များစွာပုံနှိပ်ထုတ်ဝေနိုင်လိမ့်မည်။ ဒါကြောင့် node များကိုထပ်ခါတလဲလဲမဖြစ်စေနိုင်အောင်နယ်နိမိတ်မြင်ကွင်းကိုပုံနှိပ်ပါ။

နမူနာ  

တွယ်အပ်

2 3 5 6 4 7

ရှင်းလင်းချက်

ဤတွင် node အားလုံးသည်နယ်နိမိတ် node များဖြစ်သည်။ သို့သော်ကျွန်ုပ်တို့သည် node များကိုနာရီလက်တံဆန့်ကျင်သောလမ်းကြောင်းဖြင့်ပုံနှိပ်ရန်လိုအပ်သည်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည် 2 ဖြစ်သော root မှစတင်သည်။ ထို့နောက်ကျွန်ုပ်တို့သည်တူညီသောပုံစံဖြင့်ရွေ့လျားပြီး node များ ၂၊ ၃၊ ၄၊ ၆၊ ၄၊ ၇ ကိုပုံနှိပ်ထုတ်ဝေသည်။

binary သစ်ပင်၏နယ်နိမိတ်ဖြတ်သန်းတွယ်အပ်

5 7 9 1 4 3

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

ပြproblemနာကသစ်ပင်၏နယ်နိမိတ်ကိုပုံနှိပ်ရန်ကျွန်ုပ်တို့အားတောင်းဆိုသည်၊ ဒီမှာကျွန်ုပ်တို့ဘယ်၊ ညာ၊ သစ်ပင်ဘယ်ဘက်သို့မဟုတ်ညာဘက်နယ်နိမိတ်မဆိုရှိပါက။ root သူ့ဟာသူဘယ်ဘက်သို့မဟုတ်ညာဘက်နယ်နိမိတ်အဖြစ်စဉ်းစားသည်။ အကယ်၍ ကျွန်ုပ်တို့သည်နယ်နိမိတ် node များကိုပုံနှိပ်ပါက node နှစ်ခုအနက်မှမည်သည့်အကြိမ်ရေပုံနှိပ်ထုတ်ဝေမည်ကိုဂရုမပြုသင့်သောအခြေအနေတစ်ခုရှိသေးသည်။

လည်းကြည့်ရှုပါ
Binary Tree တွင်အများဆုံး Level sum ကိုရှာပါ

ပြtheနာကိုဖြေရှင်းရန်သစ်ပင်၏ဘယ်ဘက်နယ်နိမိတ်မှစပါမည်။ node ကိုဘယ်ဘက်ခြမ်းမှမြင်နိုင်လျှင် node သည်ဘယ်ဘက်နယ်နမိတ်နှင့်သက်ဆိုင်သည်ဟုကျွန်ုပ်တို့ပြောကြသည်။ အလားတူစွာကျွန်ုပ်တို့သည်လက်ျာဘက်ခြမ်း node များနှင့် leaf node များကိုသတ်မှတ်သည်။ လက်ဝဲနယ်နိမိတ်ကိုပုံနှိပ်ရန်ကျွန်ုပ်တို့သည်အမြစ်ကိုလက်ဝဲ node တစ်ခုရှိပါက၎င်းကိုအခြားညာဘက်သို့သွားရန်ထိုကဲ့သို့သောလမ်းဖြင့်ဖြတ်သွားလိမ့်မည်။ ပြီးတာနဲ့ကျနော်တို့အရွက် node ကိုရလိမ့်မယ်။ ကျွန်ုပ်တို့သည်အရွက် node များကိုသီးခြားပုံနှိပ်သောကြောင့်ကျွန်ုပ်တို့သည်အရွက် node များကိုပုံနှိပ်ခြင်းမပြုပါ။ ပြီးတာနဲ့ကျနော်တို့လက်ဝဲနယ်နိမိတ်နှင့်အတူအမှုကိုပြုနေကြသည်။

ဘယ်ဘက် subtree ရွက်များကိုပထမ ဦး ဆုံးအကြိမ်ပုံနှိပ်ခြင်းဖြင့်ကျွန်ုပ်တို့သည်အရွက် node များကိုပုံနှိပ်သည်။ ဘယ်ဘက် subtree ရွက်များကိုပုံနှိပ်ပြီးနောက်လက်ျာ subtree ၌အရွက်ကိုပုံနှိပ်ပါ။ ဤနည်းအားဖြင့်အရွက် node များအားလုံးကိုလက်ယာရစ်နာရီမှပုံနှိပ်လိမ့်မည်။ အရွက်များကိုကျွန်ုပ်တို့ပုံနှိပ်သည်နှင့်တပြိုင်နက်ကျွန်ုပ်တို့သည်ညာဘက်နယ်နိမိတ်ရှိ node များကိုပုံနှိပ်သည်။ ဤတစ်ကြိမ်တွင် node များကိုအောက်ခြေမှပုံနှိပ်ထုတ်ဝေရန်လိုအပ်သည်။ အရှင်အတွင်း၌ ပြန်လည်ပထမ ဦး ဆုံးသစ်ပင်၏ဘယ်သို့မဟုတ်ညာ subtree ကိုဖြေရှင်းပြီးလျှင်လက်ရှိ node ကို pMicrrint ။

binary tree ၏ Boundary Traversal ကို print ထုတ်ရန် C ++ code  

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

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

// print the leaves (nodes from the bottom)
void printLeaves(node* root)
{
  if(root){
    // recursively solve the problem for the left subtree
    printLeaves(root->left);
    // if current node is a leaf
    if ((root->left) == NULL && (root->right) == NULL)
      cout<<root->data<<" ";
    // recursively solve the problem for right subtree
    printLeaves(root->right);
  }
}

// print all the nodes of left boundary
// this function will not print the leaves viewed from left side
void printLeft(node* root)
{
  if(root){
    if(root->left != NULL){
      cout<<root->data<<" ";
      // recursively move down the left subtree
      printLeft(root->left);
    }
    else if(root->right){
      cout<<root->data<<" ";
      // recursively move down the right subtree
      printLeft(root->right);
    }
  }
}

// print all the nodes of right boundary
// this function will not print the leaves viewed from the right side
void printRight(node* root)
{
  // printing is done after moving down the tree
  // thus printing is done in bottom up manner
  if(root){
    if (root->right) {
      printRight(root->right);
      cout<<root->data<<" ";
    }
    else if (root->left) {
      printRight(root->left);
      cout<<root->data<<" ";
    }
  }
}

void boundaryUtil(node* root)
{
  // first print the root, then print the left boundary
  // then the leaves which are seen from bottom
  // at last print the right boundary
  if(root){
    cout<<root->data<<" ";
    printLeft(root->left);
    printLeaves(root->left);
    printLeaves(root->right);
    printRight(root->right);
  }
}

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

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);

  boundaryUtil(root);
}
5 7 9 1 4 3

binary tree ၏ Boundary Traversal ကို print ထုတ်ရန် Java code  

import java.util.*;

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

class Main{

  // print the leaves (nodes from the bottom)
  static void printLeaves(node root)
  {
    if(root != null){
      // recursively solve the problem for the left subtree
      printLeaves(root.left);
      // if current node is a leaf
      if ((root.left) == null && (root.right) == null)
        System.out.print(root.data+" ");
      // recursively solve the problem for right subtree
      printLeaves(root.right);
    }
  }

  // print all the nodes of left boundary
  // this function will not print the leaves viewed from left side
  static void printLeft(node root)
  {
    if(root != null){
      if(root.left != null){
        System.out.print(root.data+" ");
        // recursively move down the left subtree
        printLeft(root.left);
      }
      else if(root.right != null){
        System.out.print(root.data+" ");
        // recursively move down the right subtree
        printLeft(root.right);
      }
    }
  }

  // print all the nodes of right boundary
  // this function will not print the leaves viewed from the right side
  static void printRight(node root)
  {
    // printing is done after moving down the tree
    // thus printing is done in bottom up manner
    if(root != null){
      if(root.right != null){
        printRight(root.right);
        System.out.print(root.data+" ");
      }
      else if(root.left != null){
        printRight(root.left);
        System.out.print(root.data+" ");
      }
    }
  }

  static void boundaryUtil(node root)
  {
    // first print the root, then print the left boundary
    // then the leaves which are seen from bottom
    // at last print the right boundary
    if(root != null){
      System.out.print(root.data+" ");
      printLeft(root.left);
      printLeaves(root.left);
      printLeaves(root.right);
      printRight(root.right);
    }
  }

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

  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);

    boundaryUtil(root);
  }
}
5 7 9 1 4 3

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

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

အို (N)၊ ဘာဖြစ်လို့လဲဆိုတော့ငါတို့ကသစ်ပင်ရဲ့ node အားလုံးဖြတ်သန်းသွားပြီ။ ကျွန်ုပ်တို့သည် printLeft, printRight နှင့် printLeaves function ကိုသုံးသောအခါ node များဖြတ်သန်းသွားသည်။ ထို့ကြောင့်အချိန်ရှုပ်ထွေးမှုမှာ linear ဖြစ်သည်။

လည်းကြည့်ရှုပါ
၎င်းအားချိတ်ဆက်ထားသောစာရင်းကိုယ်စားပြုမှုမှပြီးပြည့်စုံသော Binary Tree ကိုတည်ဆောက်ပါ

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

အို (H)၊ ဘယ်မှာ H သစ်ပင်၏အမြင့်သည်။ ဘာဖြစ်လို့လဲဆိုတော့ compiler stack space ကိုသုံးလို့ပါ။ နှင့် boundary element တွေကိုပုံနှိပ်ဖို့အသုံးပြုတဲ့ function တွေက compiler stack အတွက်တွက်ချက်တဲ့ recursion ကိုသုံးတယ်။