C++のプレオーダートラバーサルからBSTのポストオーダートラバーサルを検索します

この問題では、二分探索木のプレオーダートラバーサルを表す配列preOrder[]が与えられます。私たちのタスクは、プレオーダートラバーサルからBSTのポストオーダートラバーサルを見つけることです。

問題を理解するために例を見てみましょう

入力

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

出力

{4, 2, 12, 7, 5}

ソリューションアプローチ

この問題の簡単な解決策は、指定されたプレオーダートラバーサルからBSTを作成することです。そして、ツリーのポストオーダートラバーサルを実行します。この解決策は問題ありませんが、より効果的な解決策は

値に制限があるプレオーダー配列をトラバースして、左右のサブツリーの値を分離します。

トラバーサルの順序は-

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

問題を解決するもう1つの方法は、反復を使用することです。ルート->左->右のプレオーダーとpostOrderは左->右->ルートであることがわかっています。これは、ループを使用して、左側の要素の最後の要素があるピボット要素を計算することで計算できます。これを使用して、最初に左、次に右、次にルートを印刷します。

ピボットは、ルートよりも小さい大きな要素のインデックスを見つけることによって見つけられます。

ソリューションの動作を説明するプログラム

例

#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