C++で指定されたレベル順序トラバーサルからBSTを構築します

1つのレベルの順序トラバーサルがあるとします。このトラバーサルから。ツリーを生成する必要があるため、トラバーサルが[7、4、12、3、6、8、1、5、10]の場合、ツリーは-

これを解決するために、再帰的アプローチを使用します。最初の要素はルートになります。 2番目の要素は左の子になり、3番目の要素は右の子になります（BSTの条件が満たされる場合）、このプロパティはすべての要素で満たされます。したがって、次の手順に従います-

• 最初に、配列の最初の要素を取得し、これをルートにする必要があります。

• 次に、2番目の要素を取ります。それがルートよりも小さい場合は、左の子にし、そうでない場合は右の子にします

• 次に、ステップ2を再帰的に呼び出して、BSTを作成します。

例

#include <iostream>
using namespace std;
class Node {
   public:
   int data;
   Node *left, *right;
};
Node* getNode(int data) {
   Node *newNode = new Node;
   newNode->data = data;
   newNode->left = newNode->right = NULL;
   return newNode;
}
Node *lvlOrd(Node *root , int data) {
   if(root==NULL){
      root = getNode(data);
      return root;
   }
   if(data <= root->data)
      root->left = lvlOrd(root->left, data);
   else
      root->right = lvlOrd(root->right, data);
   return root;
}
Node* makeTree(int arr[], int n) {
   if(n==0)
      return NULL;
   Node *root= NULL;
   for(int i=0;i<n;i++)
   root = lvlOrd(root , arr[i]);
   return root;
}
void inord(Node* root) {
   if (!root)
      return;
   inord(root->left);
   cout << root->data << " ";
   inord(root->right);
}
int main() {
   int arr[] = {7, 4, 12, 3, 6, 8, 1, 5, 10};
   int n = sizeof(arr) / sizeof(arr[0]);
   Node *root = makeTree(arr, n);
   cout << "Inorder Traversal: ";
   inord(root);
}

出力

Inorder Traversal: 1 3 4 5 6 7 8 10 12