C++でBSTのプレオーダートラバーサルを使用したルートよりも小さい要素の数

事前注文トラバーサルの結果が表示されます。ルートよりも小さい要素の数を見つける必要があります。

プレオーダートラバーサルの最初の要素は、BSTのルートです。例を見てみましょう。

入力

preorder_result = [5, 4, 2, 1, 7, 6, 8, 9]

出力

3

ルートよりも小さい要素が3つあります。ルートは5です。

アルゴリズム

• 事前注文の結果を配列で初期化します。

• 最初の要素、つまりBSTのルートを変数に格納します。

• 事前注文結果の2番目の要素から繰り返すループを記述します。

  • すべての要素をルートと比較します。

  • 現在の要素がルートより大きい場合は、カウントを増やします。

• カウントを返します。

実装

以下は、C++での上記のアルゴリズムの実装です

#include <bits/stdc++.h>
using namespace std;
int getElementsCount(int arr[], int n) {
   if (n < 0) {
      return 0;
   }
   int i, root = arr[0], count = 0;
   for(i = 1; i < n; i++) {
      if(arr[i] < root) {
         count += 1;
      }
   }
   return count;
}
int main() {
   int preorder[] = {5, 4, 2, 1, 7, 6, 8, 9};
   int n = 8;
   cout << getElementsCount(preorder, n) << endl;
   return 0;
}

出力

上記のコードを実行すると、次の結果が得られます。

3