Урьдчилан захиалахаас BST-ийн дараахь дарааллыг олж мэд  


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Амазоны Фуркайт PayU
Хоёртын хайлтын мод Мод хөндлөн гарах

Асуудлын мэдэгдэл  

"Урьдчилан захиалахаас BST-ийн дараахь захиалгын дамжуулалтыг олох" гэсэн асуудалд танд хоёртын хайлтын модны урьдчилсан захиалга өгөхийг зааж өгсөн болно. Дараа нь өгөгдсөн оролтыг ашиглан шуудангийн хөндлөн огтлолыг олоорой.

Жишээ нь  

Урьдчилан захиалахаас BST-ийн дараахь дарааллыг олж мэдPin  

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

арга барил  

Өгөгдсөн асуудал нь бид хоёртын хайлтын модны урьдчилсан захиалгын дарааллыг хангаж өгсөн гэж хэлж байна. Одоо бид оролттой адил урьдчилсан захиалгатай урттай модны шуудангийн хөндлөн огтлолыг олох шаардлагатай байна. Энэ асуудлыг бид үр дүнтэй шийдвэрлэх шаардлагатай байна.

Гэнэн хандлага бол эхлээд preorder хөндлөн гарах ба барих BST. Дараа нь энэ шинээр босгосон модон дээр шуудангийн хөндлөн огтлолцол хий. Гэхдээ энэ арга нь орон зайн хувьд үр ашиггүй юм. Учир нь барьсан мод нь нэмэлт үүрэг гүйцэтгэдэг.

Асуудлыг үр дүнтэй шийдвэрлэхийн тулд бид оролтын массивыг дамжина. Оролтын массив нь бидний урьдчилсан захиалга юм. Тиймээс бид урьдчилсан захиалгын дагуу явж, одоогийн элемент худлаа байх ёстой эсэхийг олж мэдээрэй. Эхний элементээс эхлэхдээ хамгийн бага бүхэл тооноос бүхэл тоон утгын хоорондох хязгаарыг тохируулна. Урьдчилан захиалах хөндлөн огтлол нь зүүн, баруун дэд модны урд үндэстэй байдаг. Хэрэв зүүн дэд мод байвал элементүүд нь хамгийн бага бүхэл тооноос үндэсээс бага утга хүртэл байх ёстой гэдгийг бид мэднэ. Үүнтэй адилаар баруун дэд модны хувьд илүү их язгуураас хамгийн их бүхэл утга хүртэл байх ёстой. Одоо одоогийн элемент энэ хязгаарт ороогүй бол. Дараа нь нөгөө дэд модонд байх ёстой (хэрэв энэ нь зүүн дэд модны хувьд баруун дэд модонд хэвтэхээс холгүй байвал).

мөн үзнэ үү
Хоёртын модноос хамгийн дээд түвшний нийлбэрийг ол

код  

BST-ийн урьдчилсан дамжуулалтаас хойшхи бичлэгийг хөндлөн гарахад зориулсан 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

Урьдчилсан захиалгаас BST-ийн дараах захиалгын дамжуулалтыг олох Java код

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

Нарийн төвөгтэй байдлын шинжилгээ  

Цаг хугацааны нарийн төвөгтэй байдал

O (N)Учир нь бид өгөгдсөн массивыг бүхэлд нь туулах хэрэгтэй.

Сансрын нарийн төвөгтэй байдал

O (N), рекурсив функцэд ашиглаж байгаа хөрвүүлэгч стекээс болж.