ค้นหา postorder traversal ของ BST จาก preorder traversal ใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ preOrder[] ที่แสดงถึงการข้ามผ่านของการสั่งซื้อล่วงหน้าของทรีการค้นหาแบบไบนารี งานของเราคือค้นหาการข้ามผ่านรายการสั่งซื้อหลังการสั่งซื้อของ BST จากการส่งผ่านการสั่งซื้อล่วงหน้า

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

อินพุต

preOrder[] = {5, 2, 4, 7, 12}

ผลลัพธ์

{4, 2, 12, 7, 5}

แนวทางการแก้ปัญหา

วิธีแก้ปัญหาอย่างง่ายคือการสร้าง BST จากการข้ามผ่านของการสั่งซื้อล่วงหน้าที่กำหนด แล้วทำการขวางทาง postorder ของต้นไม้ วิธีแก้ปัญหานี้ใช้ได้ แต่วิธีแก้ปัญหาที่มีประสิทธิภาพมากกว่าคือ

เราจะสำรวจอาร์เรย์ที่สั่งซื้อล่วงหน้าโดยจำกัดค่าเพื่อแยกค่าของทรีย่อยด้านซ้ายและขวา

ลำดับการข้ามผ่านคือ −

preOrder : Root -> Left -> Right
postOrder : Left -> Right -> Root

สำหรับองค์ประกอบแรกในการสั่งซื้อล่วงหน้าซึ่งเป็นองค์ประกอบรูท สำหรับสิ่งนี้ ขีดจำกัดคือ {INT_MIN, Root} จากนั้นสำรวจอาร์เรย์ที่สั่งซื้อล่วงหน้าและองค์ประกอบแรก และสลับองค์ประกอบทั้งหมดที่จำกัดด้วยค่าสุดท้ายของขีดจำกัด ในทำนองเดียวกัน เราจะทำสิ่งนี้สำหรับทรีย่อยด้านขวาและเพิ่มรูทในตอนท้าย

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#include <iostream>
using namespace std;
void findPostOrderTraversalRec(int pre[], int n, int lowerLimit, int
upperLimit, int& index){
   if (index == n)
      return;
   if (pre[index] < lowerLimit || pre[index] > upperLimit)
      return;
   int currNode = pre[index];
   index++;
   findPostOrderTraversalRec(pre, n, lowerLimit, currNode, index);
   findPostOrderTraversalRec(pre, n, currNode, upperLimit, index);
   cout<<currNode<<" ";
}
void findPostOrderTraversalFromPreOrder(int pre[], int n){
   int index = 0;
   findPostOrderTraversalRec(pre, n, -1000, 1000, index);
}
int main(){
   int pre[] = { 5, 2, 4, 7, 12 };
   int n = sizeof(pre) / sizeof(pre[0]);
   cout<<"PreOrder Traversal : \t";
   for(int i = 0; i < n ; i++)
      cout<<pre[i]<<" ";
   cout<<endl<<"Post Order Traversal : \t";
   findPostOrderTraversalFromPreOrder(pre, n);
   return 0;
}

ผลลัพธ์

PreOrder Traversal − 5 2 4 7 12
Post Order Traversal − 4 2 12 7 5

อีกวิธีหนึ่งในการแก้ปัญหาคือการใช้การวนซ้ำ อย่างที่เราทราบกันดีว่าการสั่งซื้อล่วงหน้าใน root -> left -> right และ postOrder is left -> right -> root สามารถคำนวณได้โดยใช้การวนซ้ำและคำนวณองค์ประกอบเดือยซึ่งเป็นองค์ประกอบสุดท้ายขององค์ประกอบด้านซ้าย เมื่อใช้สิ่งนี้ เราจะพิมพ์ทางซ้ายก่อน จากนั้นไปทางขวา จากนั้นจึงทำการรูท

พบเดือยโดยการค้นหาดัชนีขององค์ประกอบที่ใหญ่กว่าซึ่งมีขนาดเล็กกว่ารูท

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#include <iostream>
using namespace std;
void findPostOrderTraversalFromPreOrder(int pre[], int n){
   int pivot = 0;
   for(int i = 1; i < n; i++){
      if (pre[0] <= pre[i]) {
         pivot = i;
         break;
      }
   }
   for(int i = pivot - 1; i > 0; i--){
      cout << pre[i] << " ";
   }
   for(int i = n - 1; i >= pivot; i--) {
      cout << pre[i] << " ";
   }
   cout << pre[0];
}
int main(){
   int pre[] = { 5, 2, 4, 7, 12 };
   int n = sizeof(pre) / sizeof(pre[0]);
   cout<<"PreOrder Traversal : \t";
   for(int i = 0; i < n ; i++)
      cout<<pre[i]<<" ";
   cout<<endl<<"Post Order Traversal : \t";
   findPostOrderTraversalFromPreOrder(pre, n);
   return 0;
}

ผลลัพธ์

PreOrder Traversal − 5 2 4 7 12
Post Order Traversal − 4 2 12 7 5