特定の配列が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