Гузариши баъдиқатли BST-ро аз гардиши пешакӣ ёбед


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Amazon Фуркайтҳо PayU
Дарахти ҷустуҷӯи бинарӣ Траверсал дарахт

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

Масъалаи "Пайдо кардани пас аз фармоиш аз BST аз гардиши пешакӣ" изҳор мекунад, ки ба шумо убури пешакии дарахти ҷустуҷӯи дуӣ дода мешавад. Пас аз истифодаи вуруди додашуда гузариши почтаро пайдо кунед.

мисол

Гузариши баъдиқатли BST-ро аз гардиши пешакӣ ёбед

preorder traversal sequence: 5 2 1 3 4 7 6 8 9
1 4 3 2 6 9 8 7 5

усул

Масъалаи додашуда мегӯяд, ки ба мо пайдарпаии гардиши пешакии дарахти ҷустуҷӯии дуӣ дода шудааст. Ҳоло аз мо талаб карда мешавад, ки убури пас аз дарахтро, ки ҳамон гузариши пешакӣ бо вуруд дорад, пайдо кунем. Аз мо талаб карда мешавад, ки ин масъаларо самаранок ҳал кунем.

Усули соддалавҳона истифодаи аввал аз пешфармоиш гузариш ва сохтани БАС. Пас аз ин дарахти навбунёд пасравӣ кунед. Аммо ин равиш нисбати фазо бесамар аст. Зеро дарахти сохташуда ҳамчун болопӯш амал мекунад.

Барои ҳалли самараноки масъала, мо массиви вурудро мегузарем. Массиви вуруд ин убури пешакии мо мебошад. Ҳамин тариқ, мо аз тарси пешакӣ гузашта, мефаҳмем, ки оё унсури ҷорӣ бояд дурӯғ гӯяд. Вақте ки мо аз унсури аввал оғоз мекунем, аз диапазони ҳадди ақалл то арзиши максималии бутун диапазон таъин менамоем. Азбаски гардиши қабл аз фармоиш решаи пеш аз зери дарахти чап ва рост дорад. Мо медонем, ки агар дарахти чап вуҷуд дошта бошад, пас унсурҳо бояд аз арзиши ададии ҳадди ақалл то арзиши камтар аз реша дур шаванд. Ба ҳамин монанд, барои зергурӯҳи рост, ки бояд аз арзиши решаи калон то арзиши максималии бутун бошад. Акнун агар унсури ҷорӣ дар ин диапазон ҷойгир набошад. Пас, он бояд дар зери дарахти дигар қарор гирад (яъне агар он дар зери дарахти чап дар доираи диапазон набошад, назар ба он ки дар зери дарахти рост ва баръакс).

рамз

Коди C ++ барои ёфтани убури пас аз фармоиш аз BST аз гардиши пешакӣ

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

void preToPost(int input[], int n, int mn, int mx, int& idx)
{
  // base case
  if (idx == n)
    return;
  // if current element does not belong to current subtree
  if (input[idx] < mn || input[idx] > mx) {
    return;
  }

  // store the value of root ro print after printing its subtrees
  int root = input[idx];
  idx++;

  // recursively solve for left and right subtree
  preToPost(input, n, mn, root, idx);
  preToPost(input, n, root, mx, idx);
  // print root
  cout<<root<<" ";
}

int main()
{
  int input[] = {5, 2, 1, 3, 4, 7, 6, 8, 9};
  int n = (sizeof input)/(sizeof input[0]);
  int idx = 0;
  	preToPost(input, n, INT_MIN, INT_MAX, idx);
}
1 4 3 2 6 9 8 7 5

Рамзи Java барои дарёфти убури пас аз фармоиш аз BST аз убури пешакӣ

import java.util.*;

class Main{
  static int idx = 0;
  static void preToPost(int input[], int n, int mn, int mx)
  {
    // base case
    if (idx == n)
      return;
    // if current element does not belong to current subtree
    if (input[idx] < mn || input[idx] > mx) {
      return;
    }

    // store the value of root ro print after printing its subtrees
    int root = input[idx];
    idx++;

    // recursively solve for left and right subtree
    preToPost(input, n, mn, root);
    preToPost(input, n, root, mx);
    // print root
    System.out.print(root+" ");
  }

  public static void main(String[] args)
  {
    int input[] = {5, 2, 1, 3, 4, 7, 6, 8, 9};
    int n = input.length;
    	preToPost(input, n, Integer.MIN_VALUE, Integer.MAX_VALUE);
  }
}
1 4 3 2 6 9 8 7 5

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

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

О (Н), зеро мо бояд тамоми массиви додашударо тай кунем.

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

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