Preorder traversal مان BST جو پوسٽ مارٽر ٽرورس ڳوليو


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Amazon چار چار پي يو يو
ثنائي ڳولا وارو وڻ وڻ ٽرانسورس

مسئلي جو بيان

مسئلو “Preorder traversal from BST جي postorder traversal ڳوليو” ٻڌائي ٿو ته توهان کي بائنري سرچ وڻ جي اڳ-آرڊر traversal ڏنو ويو آهي. پوءِ ڏنل آندل استعمال ڪندي پوسٽريڊر ٽراسلال ڳوليو.

مثال

Preorder traversal مان BST جو پوسٽ مارٽر ٽرورس ڳوليو

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

چرچو

ڏنل مسئلو چوي ٿو ته اسان کي بائنري سرچ وڻ جي اڳئين ترتيب جي طويل ترتيب سان مهيا ڪئي وئي آهي. هاڻ اسان کي گهربل آهي ته وڻ جي پوئين آرڊر ٽرورس کي ڳولهيو جنهن ۾ اڳئين درجي جي اڳواٽ بهاني هجي. اسان کي گهربل آهي ته هن مسئلي کي موثر طريقي سان حل ڪيو وڃي.

هڪ غير معمولي طريقو پهريون ڀيرو استعمال ڪرڻ جي آهي پھريان طويل ۽ تعمير ڪريو BST. پوءِ بس هن نئين تعمير ٿيل وڻ مٿان پوئين آرڊر ٽرورس. پر اهو نقشو خلا بابت غير موثر آهي. ڇاڪاڻ ته ٺاهيل وڻ هڪ ٻوڙي جي مٿان عمل ڪري رهيو آهي.

مسئلي کي موثر طريقي سان حل ڪرڻ لاءِ ، اسان ان پُٽ صف ذريعي وڃون ٿا. ان پٽ لار اسان جي اڳئين ٽراٽل آهي. تنهنڪري اسان اڳوڻي پريزر ٽورسل ذريعي وڃون ٿا ۽ ڳولون ٿا ته موجوده عنصر ڪوڙ ڪرڻ گهرجي. جڏهن اسان پهريون عنصر سان شروع ڪندا آهيون اسين حد کان گھٽ انٽيگر ويل کان وڌ کان وڌ عدد تائين مقرر ڪندا آهيون. ڇو ته پريڊر ٽريورس وٽ روٽ اڳ کان کاٻي ۽ سا subي سبٽيري کان اڳ آهي. اسان thatاڻون ٿا ته جيڪڏھن کاٻي شاخ موجود آھي ته عنصرن گھٽ ۾ گھٽ انٽيگريٽي قدر کان جڙ تائين گھٽ ويليو تائين وڃي سمجھن. ساڳي طرح صحيح ساtي لاءِ جنهن کي وڌ کان وڌ اڪثريت جي وڏي روٽ جي قدر کان ڪوٽي وڃڻ گهرجي. هاڻي جيڪڏهن موجوده عنصر انهي حد ۾ ڪوڙ نه آهي. ته پوءِ اها ٻين سبٽيري ۾ ڪوڙ ڪرڻ گهرجي (اهو آهي ته جيڪڏهن اهو نن leftو سبٽيري ۾ رينج ۾ ڪوڙ ناهي ڳالهائجي ته ان کي سا subي سبٽيري ۾ ۽ انهي جي برعڪس هئڻ گهرجي)

ڪوڊ

پري آرڊر ٽرورسال کان بي ٽي ايس جي پوسٽ آرڊر ٽرورس ڳولڻ لاءِ C ++ ڪوڊ

#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

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (اين)، ڇاڪاڻ ته اسان کي پوري ڏنل سيٽ کي رد ڪرڻ گهرجي.

خلائي پيچيدگي

اي (اين)ڇاڪاڻ ته مرتب ڪندڙ اسٽيڪ جي ڪري ، جيڪا اعصابي ڪمن لاءِ استعمال ٿي رهي آهي.