Xây dựng BST từ truyền tải đặt hàng trước đã cho - Đặt 2 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 vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo ngăn xếp trống

• Đặt giá trị đầu tiên làm giá trị gốc và đẩy nó vào ngăn xếp.

• Bây giờ, hãy tiếp tục pooping trong khi ngăn xếp không trống và giá trị tiếp theo lớn hơn phần tử trên cùng của ngăn xếp, hãy đặt nó làm phần tử con bên phải của nút bật lên cuối cùng. Bây giờ, hãy đẩy nút mới vào ngăn xếp.

• Khi giá trị tiếp theo nhỏ hơn phần tử trên cùng, hãy đặt nó làm phần tử con bên trái của phần tử trên cùng của ngăn xếp. Bây giờ hãy đẩy nút mới vào ngăn xếp.

• Lặp lại các bước 2 và 3 cho đến khi chúng tôi đã kiểm tra tất cả các phần tử của danh sách đặt hàng trước.

Ví dụ

#include <iostream>
#include <stack>
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* constructTree ( int pre[], int size ) {
   stack<node*> stk;
   node* root = getNode( pre[0] );
   stk.push(root);
   int i;
   node* temp;
   for ( i = 1; i < size; ++i ) {
      temp = NULL;
      while ( !stk.empty() && pre[i] > stk.top()->data ) {
         temp = stk.top();
         stk.pop();
      }
      if ( temp != NULL) {
         temp->right = getNode( pre[i] );
         stk.push(temp->right);
      } else {
         node* peek_node = stk.top();
         peek_node->left = getNode( pre[i] );
         stk.push(stk.top()->left);
      }
   }
   return root;
}
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 = constructTree(pre, size);
   cout << "Inorder traversal: ";
   inord(root);
}

Đầu ra

Inorder traversal: 1 5 7 10 40 50