Давраи сарҳадии дарахти дуӣ


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Accolite Amazon саёҳат кардан Solutions Kritikal Microsoft Morgan Stanley PayU Snapdeal
Дарахти дуӣ Дарахт Траверсал дарахт

Изҳороти мушкилот

Масъалаи "Гузариши сарҳадии дарахти дуӣ" мегӯяд, ки ба шумо дарахти дуӣ дода мешавад. Акнун ба шумо лозим аст, ки намуди ҳудуди a -ро чоп кунед дарахти дуӣ. Дар ин ҷо убури сарҳад маънои онро дорад, ки ҳамаи гиреҳҳо ҳамчун сарҳади дарахт нишон дода шудаанд. Гиреҳҳо аз тарафи боло, тарафи чап, поён ва тарафи рост дар самти зидди соат ба назар мерасанд. Аммо агар мо ҳамаи ин дидгоҳҳоро мустақиман чоп мекардем, ки дар натиҷа чопи як гиреҳ якчанд маротиба ба амал меомад. Пас, намуди сарҳадро тавре чоп кунед, ки гиреҳҳо такрор нашаванд.

мисол

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

Рамзи Java барои чопи сарҳадии дарахти дуӣ

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

Таҳлили мураккабӣ

Мураккабии вақт

O (N), зеро мо аз тамоми гиреҳҳои дарахт гузаштаем. Ҳангоми истифодаи функсияи printLeft, printRight ва printLeaves мо аз гиреҳҳо мегузарем. Ҳамин тавр мураккабии вақт хатӣ аст.

Мураккабии фазо

О (Н), ки дар он H баландии дарахт аст. Сабаб ин аст, ки стаки тартибдиҳанда фазоро истифода мебарад. Ва функсияҳое, ки барои чопи унсурҳои ҳудудӣ истифода мешаванд, рекурсияро истифода мебаранд, ки барои стеки компилятор ҳисоб карда мешавад.