Пронађите прелазак БСТ-а по поруџбини из преусмеравања пре-налога


Ниво тешкоће Средњи
Често питани у амазонка Фоуркитес ПаиУ
Бинарно стабло претраживања Прелазак дрвета

Изјава о проблему

Проблем „Пронађи преокрет БСТ-а из поруџбине преусмеравања“ наводи да вам је дато преусмеравање поруџбине бинарног стабла претраживања. Затим помоћу датог уноса пронађите прелазак по редоследу.

Пример

Пронађите прелазак БСТ-а по поруџбини из преусмеравања пре-налога

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

Приступ

Дати проблем каже да нам је обезбеђен редослед заокретања унапред поруџбине бинарног стабла претраживања. Сада се од нас тражи да пронађемо преусмјеравање постордера стабла које има исти прелаз поруџбине као улаз. Од нас се захтева да ефикасно решимо овај проблем.

Наиван приступ је прво користити преордер преокрет и изградити ЦДТ. Затим једноставно извршите прелазак постордером преко овог новоизграђеног дрвета. Али овај приступ је неефикасан у погледу простора. Зато што конструисано дрво делује као режија.

Да бисмо ефикасно решили проблем, пролазимо кроз улазни низ. Улазни низ је наша преусмеравања преднаруџбе. Дакле, пролазимо кроз преверзију преднаруџби и проналазимо да ли би тренутни елемент требао лежати. Када започнемо са првим елементом постављамо опсег од минималне целобројне вредности до максималне целобројне вредности. Јер преверзија преордер има корен пре левог и десног подстабла. Знамо да ако постоји лево подстабло, елементи би требало да леже од минималне целобројне вредности до вредности мање од корена. Слично за десно подстабло које треба да лежи од вредности већег корена до максималне целобројне вредности. Сада, ако тренутни елемент не лежи у овом опсегу. Тада би то требало да лежи у другом подстаблу (то јест ако не лежи у домету за лево подстабло, него што би требало да лежи у десном подстаблу и обрнуто).

код

Ц ++ код за проналажење постордер преласка БСТ из преордер преласка

#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

Јава код за проналажење преласка БСТ-а из поруџбине

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

Анализа сложености

Сложеност времена

НА), јер морамо прећи цео дати низ.

Сложеност простора

НА), због стека компајлера који се користи за рекурзивне функције.