የድንበር መተላለፊያ የሁለትዮሽ ዛፍ  


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ የተከማቸ አማዞን ረጅም መንገድ ተንሸራሸረ ክሪቲካል መፍትሔዎች የ Microsoft ሞርጋን ስታንሊ PayU Snapdeal
ሁለትዮሽ ዛፍ ዛፍ የዛፍ ተሻጋሪ

የችግሩ መግለጫ  

ችግሩ “የሁለትዮሽ ዛፍ ድንበር ተሻጋሪ” የሁለትዮሽ ዛፍ ይሰጥዎታል ይላል። አሁን የ ‹ሀ› ወሰን እይታ ማተም ያስፈልግዎታል ሁለትዮሽ ዛፍ. እዚህ ላይ ድንበር ተሻጋሪ ማለት ሁሉም አንጓዎች እንደ የዛፉ ወሰን ይታያሉ ማለት ነው ፡፡ አንጓዎቹ ከፀረ-ሰዓት አቅጣጫ በተቃራኒ ከላይ በኩል ፣ ከግራ ፣ ከግራ እና ከቀኝ በኩል ይታያሉ ፡፡ ግን እነዚህን ሁሉ እይታዎች በቀጥታ ብናተም ኖሮ ተመሳሳይ አንጓዎችን ማተም ያስገኛል ፡፡ ስለዚህ አንጓዎቹ እንዳይደገሙ የድንበሩን እይታ ያትሙ ፡፡

ለምሳሌ  

2 3 5 6 4 7

ማስረጃ

እዚህ ሁሉም አንጓዎች የድንበር አንጓዎች ናቸው ፡፡ ግን አንጓዎችን በፀረ-ሰዓት አቅጣጫ አቅጣጫ ማተም ያስፈልገናል ፡፡ ስለሆነም ከሥሩ እንጀምራለን 2. ከዚያ እኛ በቀላሉ በተመሳሳይ ሁኔታ እንንቀሳቀስ እና አንጓዎቹን 2 ፣ 3 ፣ 4 ፣ 6 ፣ 4 ፣ 7 እናተም ፡፡

የድንበር መተላለፊያ የሁለትዮሽ ዛፍ

5 7 9 1 4 3

ቀረበ  

ችግሩ የዛፉን ወሰን እንድናተም ይጠይቀናል ፣ እዚህ ግራ ፣ ቀኝ እና ታች ድንበር አለን ፡፡ ዛፉ የግራ ወይም የቀኝ ድንበር ከሌለው ፡፡ ሥሩ ራሱ እንደ ግራ ወይም ቀኝ ድንበር ተደርጎ ይወሰዳል ፡፡ እንዲሁም የድንበር አንጓዎችን ካተምን ከሁለቱ አንጓዎች አንዳቸውም ብዙ ጊዜ እንዳይታተሙ ጥንቃቄ ማድረግ አለብን የሚል አንድ ሁኔታ አለ ፡፡

ችግሩን ለመፍታት ከዛፉ የግራ ወሰን እንጀምራለን ፡፡ ያ መስቀለኛ ክፍል ከግራ በኩል ከታየ መስቀለኛ መንገድ የግራ ወሰን ነው እንላለን ፡፡ በተመሳሳይ እኛ የቀኝ የጎን አንጓዎችን እና የቅጠል አንጓዎችን እንገልፃለን ፡፡ የግራውን ወሰን ለማተም ፣ ዛፉ የግራ መስቀለኛ መንገድ ካለው ወደዚያ ወደ ሌላኛው ወደ ቀኝ መስቀሉ እንዲሄድ በሚያስችል መንገድ ዛፉን እናቋርጣለን። አንዴ ወደ ቅጠሉ መስቀለኛ ክፍል እንገባለን ፡፡ የቅጠል አንጓዎችን በተናጠል እንደገና ስለምናተም የቅጠል አንጓዎችን አናተምም ፡፡ አንዴ የግራውን ወሰን እንደጨረስን ፡፡

ተመልከት
በሁለትዮሽ ዛፍ ውስጥ ከፍተኛውን የደረጃ ድምርን ያግኙ

የግራ ንዑስ ዛፍ ቅጠሎችን እንደገና በማተም እንደገና በማደግ የቅጠሉን አንጓዎች እናተም ፡፡ የግራ ንዑስ ዛፍ ቅጠሎችን ከታተመ በኋላ ቅጠሎችን በቀኝ ንዑስ ክፍል ውስጥ ያትሙ ፡፡ በዚህ መንገድ ሁሉም የቅጠል አንጓዎች በፀረ-ሰዓት አቅጣጫ አቅጣጫ ይታተማሉ። ቅጠሎችን አንዴ ካተምነው በኋላ የቀኝ ወሰን አንጓዎችን እናተም ፡፡ በዚህ ጊዜ አንጓዎቹ ከታች ወደ ላይ በሚታተም ሁኔታ መታተም ያስፈልጋቸዋል ፡፡ ስለዚህ በ ውስጥ ተደጋጋሚነት፣ በመጀመሪያ የዛፉን ግራ ወይም ቀኝ ንዑስ ዛፍ እንፈታለን እና ከዚያ የአሁኑን መስቀለኛ መንገድ pMicrrint እናደርጋለን ፡፡

የሁለትዮሽ ዛፍ ድንበር ተሻጋሪነትን ለማተም የ C ++ ኮድ  

#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

የሁለትዮሽ ዛፍ ድንበር ተሻጋሪነትን ለማተም የጃቫ ኮድ  

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

ውስብስብነት ትንተና  

የጊዜ ውስብስብነት

ኦ (ኤን) ፣ ምክንያቱም በሁሉም የዛፉ አንጓዎች ውስጥ ተሻግረናል ፡፡ የህትመት ግራን ፣ የህትመት መብት እና የህትመት ላቭስ ተግባርን ስንጠቀም በመስቀለኛዎቹ ውስጥ እንጓዛለን ፡፡ ስለዚህ የጊዜ ውስብስብነት መስመራዊ ነው።

ተመልከት
ከተገናኘው ዝርዝር ውክልና የተሟላ የሁለትዮሽ ዛፍ ይገንቡ

የቦታ ውስብስብነት

ኦ (ኤች) ፣ H የዛፉ ቁመት ነው ፡፡ ይህ የሆነበት ምክንያት አሰባሳቢው ክምችት ቦታን ስለሚጠቀም ነው ፡፡ የድንበሩን አካላት ለማተም ያገለገሉ ተግባራት ለአቀናባሪው ቁልል የሚቆጠር ድጋሜ ይጠቀማሉ ፡፡