Tạo BST từ truyền tải đặt hàng trước đã cho - Đặt 1 trong C ++

Giả sử chúng ta có một lần duyệt đơn đặt hàng trước. Từ đường truyền này. chúng ta phải tạo ra cây Vì vậy, nếu đường truyền giống như [10, 5, 1, 7, 40, 50], thì cây sẽ giống như -

Để giải quyết điều này, chúng tôi sẽ sử dụng thủ thuật này. Mẹo là đặt một phạm vi {min… max} cho mỗi nút. Lúc đầu, chúng tôi sẽ khởi tạo phạm vi là {INT_MIN… INT_MAX}. Nút đầu tiên chắc chắn sẽ nằm trong phạm vi, vì vậy sau đó chúng ta sẽ tạo nút gốc. Để tạo cây con bên trái, hãy đặt phạm vi là {INT_MIN… root-> data}. Nếu một giá trị nằm trong phạm vi {INT_MIN… root-> data}, thì giá trị đó là một phần của cây con bên trái. Để tạo cây con bên phải, hãy đặt phạm vi là {root-> data… max… INT_MAX}.

Ví dụ

#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);
}

Đầu ra

Inorder traversal: 1 5 7 10 40 50