ද්විමය ගසේ මායිම් සංචලනය


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇසොලයිට් ඇමේසන් ඉහළ දැමීම ක්‍රිටිකල් විසඳුම් මයික්රොසොෆ්ට් මෝර්ගන් ස්ටැන්ලි PayU Snapdeal
ද්විමය ගස ගස රුක් සංචලනය

ගැටළු ප්රකාශය

“ද්විමය ගසෙහි මායිම් ගමන් කිරීම” යන ගැටලුවේ සඳහන් වන්නේ ඔබට ද්විමය ගසක් ලබා දී ඇති බවයි. දැන් ඔබ a හි මායිම් දර්ශනය මුද්‍රණය කළ යුතුය ද්විමය ගස. මෙහි මායිම් ගමන් කිරීම යනු සියලු නෝඩ් ගසේ මායිම ලෙස දැක්වේ. නෝඩ් ඉහළ පැත්තෙන්, වම් පැත්තෙන්, පහළ පැත්තෙන් සහ දකුණු පැත්තෙන් ප්‍රති-ඔරලෝසුව දිශාවකින් දැකිය හැකිය. නමුත් අපි මේ සියලු අදහස් කෙලින්ම මුද්‍රණය කළා නම් එමඟින් එකම නෝඩ් කිහිප වතාවක් මුද්‍රණය වේ. එබැවින් නෝඩ් නැවත නොකිරීමට මායිම් දර්ශනය මුද්‍රණය කරන්න.

උදාහරණයක්

2 3 5 6 4 7

පැහැදිලි කිරීම

මෙන්න, සියලුම නෝඩ් මායිම් නෝඩ් වේ. නමුත් අපි නෝඩ් ඔරලෝසුව දිශාවට මුද්‍රණය කළ යුතුයි. මේ අනුව අපි 2 වන මූලයෙන් ආරම්භ කරමු. ඉන්පසු අපි එකම ආකාරයකින් ගමන් කර 2, 3, 4, 6, 4, 7 නෝඩ් මුද්‍රණය කරමු.

ද්විමය ගසේ මායිම් සංචලනය

5 7 9 1 4 3

ප්රවේශය

ගැටළුව අපෙන් ඉල්ලා සිටින්නේ ගසෙහි මායිම මුද්‍රණය කරන ලෙසයි, මෙහි අපට වම්, දකුණ සහ පහළ මායිම ඇත. ගසෙහි වම් හෝ දකුණු මායිම කිසිවක් නොමැති නම්. මූලය වම් හෝ දකුණු මායිම ලෙස සැලකේ. මායිම් නෝඩ් මුද්‍රණය කරන්නේ නම්, නෝඩ් දෙකෙන් එකක්වත් කිහිප වතාවක් මුද්‍රණය නොකිරීමට අප වගබලා ගත යුතුය.

ගැටළුව විසඳීම සඳහා, අපි ගසෙහි වම් මායිමෙන් ආරම්භ කරමු. එම නෝඩය වම් පැත්තෙන් පෙනේ නම් නෝඩ් එකක් වම් සීමාවට අයත් බව අපි කියමු. ඒ හා සමානව, අපි දකුණු පැත්තේ නෝඩ් සහ කොළ නෝඩ් නිර්වචනය කරමු. වම් මායිම මුද්‍රණය කිරීම සඳහා, අපි ගස හරහා ගමන් කරන්නේ මූලයට වම් නෝඩයක් තිබේ නම් වෙනත් දෙසට ගමන් කර එහි දකුණු නෝඩයට ගමන් කරන්න. වරක් අපි කොළ නෝඩයට පිවිසෙමු. අපි පත්‍ර නෝඩ් වෙන වෙනම මුද්‍රණය කරන නිසා අපි කොළ නෝඩ් මුද්‍රණය නොකරමු. අප වම් මායිම සමඟ කළ පසු.

අපි පත්‍ර නෝඩ් මුද්‍රණය කරන්නේ, පුනරාවර්තන ලෙස මුලින්ම වම් උපසිරැසි කොළ මුද්‍රණය කිරීමෙනි. වම් සබ්ට්‍රී කොළ මුද්‍රණය කිරීමෙන් පසු කොළ දකුණු උප කුලයේ මුද්‍රණය කරන්න. මේ ආකාරයෙන් සියලුම පත්‍ර නෝඩ් ඔරලෝසුව දිශාවට මුද්‍රණය කෙරේ. අපි කොළ මුද්‍රණය කළ පසු, දකුණු මායිමේ නෝඩ් මුද්‍රණය කරමු. මෙවර නෝඩ් පහතින් මුද්‍රණය කළ යුතුය. මේ අනුව පුනරාවර්තනය, පළමුව අපි ගසේ වම් හෝ දකුණු උප කුලකය විසඳා පසුව වත්මන් නෝඩය pMicrrint කරන්නෙමු.

ද්විමය වෘක්ෂයේ මායිම් සංචලනය මුද්‍රණය කිරීම සඳහා සී ++ කේතය

#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

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

මත), මොකද අපි ගසේ සියලුම නෝඩ් හරහා ගමන් කළා. අපි printLeft, printRight, සහ printLeaves ශ්‍රිතය භාවිතා කරන විට අපි නෝඩ් හරහා ගමන් කරමු. මේ අනුව කාල සංකීර්ණතාව රේඛීය වේ.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (එච්), H යනු ගසේ උසයි. මෙයට හේතුව සම්පාදක තොගය අවකාශය භාවිතා කිරීමයි. මායිම් මූලද්රව්ය මුද්රණය කිරීම සඳහා භාවිතා කරන කාර්යයන් සම්පාදක තොගය සඳහා පුනරාවර්තනය භාවිතා කරයි.