C++에서 주어진 레벨 순서 순회로부터 BST 구성

하나의 레벨 순서 순회가 있다고 가정합니다. 이 순회에서. 트리를 생성해야 합니다. 따라서 순회가 [7, 4, 12, 3, 6, 8, 1, 5, 10]과 같으면 트리는 -

이를 해결하기 위해 재귀적 접근 방식을 사용합니다. 첫 번째 요소는 루트가 됩니다. 두 번째 요소는 왼쪽 자식이 되고 세 번째 요소는 오른쪽 자식이 됩니다(BST의 조건이 충족되는 경우). 이 속성은 모든 요소에 대해 충족됩니다. 따라서 우리는 다음 단계를 따를 것입니다 -

• 처음에는 배열의 첫 번째 요소를 가져와 루트로 만들어야 합니다.

• 그런 다음 두 번째 요소를 가져옵니다. 루트보다 작으면 왼쪽 자식으로, 그렇지 않으면 오른쪽 자식으로 만듭니다.

• 그런 다음 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