주어진 배열이 C++에서 이진 검색 트리의 선주문 순회를 나타낼 수 있는지 확인하십시오.

배열에 요소 목록이 있다고 가정하고 요소가 이진 검색 트리의 선주문 순회가 될 수 있는지 여부를 확인해야 합니다. 시퀀스가 {40, 30, 35, 80, 100}과 같다고 가정하면 트리는 다음과 같습니다. -

스택을 사용하여 이것을 해결할 수 있습니다. 이 문제를 해결하려면 다음 단계를 따라야 합니다.

• 빈 스택 정의
• 근을 음의 무한대로 설정
• 선주문 순서의 모든 요소에 대해 다음을 수행합니다. -
  • 요소가 현재 루트보다 작으면 false를 반환합니다.
  • 요소가 스택 상단보다 큰 동안 스택에서 요소를 계속 제거하고 마지막으로 제거된 요소를 루트로 만듭니다.
  • 요소를 스택에 푸시

예시

#include <iostream>
#include <stack>
using namespace std;
bool isValidPreorder(int pre[], int n) {
   stack<int> stk;
   int root = INT_MIN;
   for (int i=0; i<n; i++) {
      if (pre[i] < root)
         return false;
      while (!stk.empty() && stk.top()<pre[i]) {
         root = stk.top();
         stk.pop();
      }
      stk.push(pre[i]);
   }
   return true;
}
int main() {
   int pre[] = {40, 30, 35, 80, 100};
   int n = sizeof(pre)/sizeof(pre[0]);
   if(isValidPreorder(pre, n))
      cout << "This can form BST";
   else
      cout << "This can not form BST";
}

출력

This can form BST