C++의 선주문 순회에서 BST의 후위 순회 찾기

이 문제에서 우리는 이진 탐색 트리의 사전순서 순회를 나타내는 배열 preOrder[]를 받습니다. 우리의 임무는 preorder traversal에서 BST의 postorder traversal을 찾는 것입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

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

출력

{4, 2, 12, 7, 5}

솔루션 접근 방식

이 문제에 대한 간단한 해결책은 주어진 선주문 순회에서 BST를 만드는 것입니다. 그런 다음 트리의 후위 순회를 수행합니다. 이 솔루션은 괜찮지만 더 효과적인 솔루션은

왼쪽 및 오른쪽 하위 트리의 값을 구분하기 위해 값에 대한 제한이 있는 사전 주문 배열을 탐색합니다.

순회 순서는 -

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

루트 요소인 preorder의 첫 번째 요소에 대해. 이를 위한 제한은 {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

문제를 해결하는 또 다른 방법은 반복을 사용하는 것입니다. 루트 -> 왼쪽 -> 오른쪽 및 postOrder의 preorder가 왼쪽 -> 오른쪽 -> 루트라는 것을 알고 있습니다. 이것은 루프를 사용하고 왼쪽 요소의 마지막 요소가 있는 피벗 요소를 계산하여 계산할 수 있습니다. 이를 사용하여 왼쪽을 먼저 인쇄한 다음 오른쪽을 인쇄한 다음 루트를 인쇄합니다.

피벗은 루트보다 작은 큰 요소의 인덱스를 찾아서 찾습니다.

우리 솔루션의 작동을 설명하는 프로그램

예시

#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