주어진 선주문 순회에서 BST 구성 - C++에서 1 설정

하나의 사전 주문 순회가 있다고 가정합니다. 이 순회에서. 트리를 생성해야 합니다. 따라서 순회가 [10, 5, 1, 7, 40, 50]과 같으면 트리는 다음과 같습니다. -

이를 해결하기 위해 우리는 이 트릭을 사용할 것입니다. 비결은 각 노드에 대해 {min… max} 범위를 설정하는 것입니다. 처음에는 범위를 {INT_MIN… INT_MAX}로 초기화합니다. 첫 번째 노드는 확실히 범위 내에 있으므로 그 후에 루트 노드를 생성합니다. 왼쪽 하위 트리를 구성하려면 범위를 {INT_MIN… root->data}로 설정합니다. 값이 {INT_MIN… root->data} 범위에 있으면 값은 왼쪽 하위 트리의 일부입니다. 올바른 하위 트리를 구성하려면 범위를 {root->data… max… INT_MAX}로 설정하세요.

예시

#include <iostream>
using namespace std;
class node {
   public:
      int data;
      node *left;
      node *right;
};
node* getNode (int data) {
   node* temp = new node();
   temp->data = data;
   temp->left = temp->right = NULL;
   return temp;
}
node* makeTreeUtil( int pre[], int* preord_index, int key, int min, int max, int size ) {
   if( *preord_index >= size )
   return NULL;
   node* root = NULL;
   if( key > min && key < max ){
      root = getNode( key );
      *preord_index += 1;
      if (*preord_index < size){
         root->left = makeTreeUtil( pre, preord_index, pre[*preord_index], min, key, size );
         root->right = makeTreeUtil( pre, preord_index, pre[*preord_index],key, max, size );
      }
   }
   return root;
}
node *makeTree (int pre[], int size) {
   int preord_index = 0;
   return makeTreeUtil( pre, &preord_index, pre[0], INT_MIN, INT_MAX, size );
}
void inord (node* node) {
   if (node == NULL)
      return;
   inord(node->left);
   cout << node->data << " ";
   inord(node->right);
}
int main () {
   int pre[] = {10, 5, 1, 7, 40, 50};
   int size = sizeof( pre ) / sizeof( pre[0] );
   node *root = makeTree(pre, size);
   cout << "Inorder traversal: ";
   inord(root);
}

출력

Inorder traversal: 1 5 7 10 40 50