پیمایش پس از سفارش BST را از پیمایش قبل از سفارش پیدا کنید  


سطح دشواری متوسط
اغلب در آمازون فورکایت PayU
درخت جستجوی دودویی عبور از درخت

بیان مسأله  

مسئله "پیدا کردن پیمایش پس از سفارش BST از پیمایش قبل از سفارش" بیان می کند که شما به یک پیمایش پیش خرید یک درخت جستجوی دودویی داده می شوید. سپس با استفاده از ورودی داده شده مسیریابی پس از سفارش را پیدا کنید.

مثال  

پیمایش پس از سفارش BST را از پیمایش قبل از سفارش پیدا کنیدسنجاق  

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

روش  

مشکل ارائه شده می گوید که ما یک ترتیب پیمایشی از پیش خرید یک درخت جستجوی باینری ارائه می دهیم. حال ما ملزم به یافتن پیمایش پس از سفارش درخت هستیم که همان پیمایش قبل از سفارش را دارد. ما ملزم به حل کارآمد این مشکل هستیم.

یک رویکرد ساده لوحانه این است که ابتدا از پیش سفارش پیمایش و ساخت BST. سپس به سادگی روی این درخت تازه ساخته شده یک پیمایش پس از سفارش انجام دهید. اما این روش در مورد فضا ناکارآمد است. زیرا درخت ساخته شده به عنوان یک سربار عمل می کند.

برای حل موثر مسئله ، ما از آرایه ورودی عبور می کنیم. آرایه ورودی پیمایش پیش سفارش ماست. بنابراین ما از پیمایش قبل از سفارش می گذریم و می فهمیم که آیا عنصر فعلی باید دروغ باشد. هنگامی که با اولین عنصر شروع می کنیم ، محدوده ای از حداقل مقدار صحیح تا حداکثر مقدار صحیح تعیین می کنیم. زیرا پیش تراوری ریشه قبل از خرده درخت چپ و راست ریشه دارد. ما می دانیم که اگر زیر شاخه چپ وجود داشته باشد ، عناصر باید از حداقل مقدار صحیح تا مقداری کمتر از ریشه واقع شوند. به طور مشابه برای زیر درخت مناسب که باید از مقدار ریشه بیشتر تا حداکثر مقدار صحیح باشد. حال اگر عنصر فعلی در این محدوده نباشد. سپس این باید در زیر درخت دیگر قرار بگیرد (یعنی اگر برای زیر درخت چپ فاصله ای نداشته باشد بیش از آنکه در زیر درخت راست باشد و بالعکس).

همچنین مشاهده کنید
مجموع حداکثر سطح را در Binary Tree پیدا کنید

رمز  

کد ++ 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

کد جاوا برای یافتن پیمایش پس از سفارش 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

تحلیل پیچیدگی  

پیچیدگی زمان

بر)، زیرا ما باید کل آرایه داده شده را پیمایش کنیم.

پیچیدگی فضا

بر)، به دلیل پشته کامپایلر که برای توابع بازگشتی استفاده می شود.