Эки дарактын чеги


Кыйынчылык деңгээли орто
Көп суралган Accolite Amazon селсаяктоо Kritikal Solutions Microsoft Морган Стэнли PayU Snapdeal
Binary Tree дарак Tree Traversal

Маселени билдирүү

"Эки дарактын чек арасынан өтүү" көйгөйүндө сизге экилик дарак берилгендиги айтылат. Эми а-нын чек ара көрүнүшүн басып чыгаруу керек экилик дарак. Бул жерде чек арадан өтүү бардык түйүндөр дарактын чеги катары көрсөтүлгөнүн билдирет. Түйүндөр сааттын жебесине каршы багытта жогорку, сол, төмөнкү жана оң капталынан көрүнүп турат. Бирок биз ушул көрүнүштөрдүн бардыгын түз эле басып чыгармакпыз, натыйжада бир эле түйүндөр бир нече жолу басып чыгарылат. Ошентип, чек ара көрүнүшүн баскычтар кайталанбашы үчүн басып чыгарыңыз.

мисал

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 функциясын колдонгондо, биз түйүндөр аркылуу өтөбүз. Ошентип, убакыттын татаалдыгы сызыктуу.

Космостун татаалдыгы

O (H), мында H - дарактын бийиктиги. Себеби, компилятордун стеги мейкиндикти колдонот. Ал эми чек ара элементтерин басып чыгаруу үчүн колдонулган функциялар компилятор стеги үчүн эсептелген рекурсияны колдонот.