Xây dựng BST từ truyền tải thứ tự cấp đã cho của nó trong C ++

Giả sử chúng ta có duyệt đơn hàng một cấp. 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ư [7, 4, 12, 3, 6, 8, 1, 5, 10], thì cây sẽ giống như -

Để giải quyết điều này, chúng tôi sẽ sử dụng phương pháp đệ quy. Phần tử đầu tiên sẽ là gốc. Phần tử thứ hai sẽ là phần tử con bên trái và phần tử thứ ba sẽ là phần tử con bên phải (Nếu điều kiện của BST thỏa mãn), thuộc tính này sẽ được thỏa mãn cho tất cả các phần tử. Vì vậy, chúng tôi sẽ làm theo các bước sau -

• Đầu tiên, chúng ta phải lấy phần tử đầu tiên của mảng và đặt phần tử này làm phần tử gốc.

• Sau đó, lấy phần tử thứ hai. Nếu cái đó nhỏ hơn cái gốc, thì đặt nó là con trái, ngược lại là con phải

• Sau đó gọi đệ quy bước 2 để tạo BST.

Ví dụ

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

Đầu ra

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