Hướng giải của Chèn vào BST

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Hướng dẫn giải

Bài toán mô phỏng quá trình chèn vào BST và in ra đường đi. Ta xây dựng BST và với mỗi giá trị cần chèn, ta duyệt từ gốc xuống để tìm vị trí thích hợp, đồng thời ghi nhận đường đi.

Các bước thực hiện:

  1. Định nghĩa cấu trúc nút BST.
  2. Với mỗi giá trị \(a_i\):
    • Nếu cây rỗng, tạo nút gốc và in \(ROOT\).
    • Ngược lại, duyệt từ gốc, so sánh giá trị và ghi nhận các nút đã đi qua, sau đó chèn vào vị trí thích hợp.
  3. In các giá trị trên đường đi tìm được.

Độ phức tạp: \(O(N \log N)\) trung bình.

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node *left, *right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

int main() {
    int N;
    cin >> N;
    Node* root = nullptr;
    for (int i = 0; i < N; ++i) {
        int x;
        cin >> x;
        if (!root) {
            root = new Node(x);
            cout << "ROOT\n";
            continue;
        }
        vector<int> path;
        Node* cur = root;
        while (true) {
            path.push_back(cur->val);
            if (x < cur->val) {
                if (!cur->left) {
                    cur->left = new Node(x);
                    break;
                }
                cur = cur->left;
            } else {
                if (!cur->right) {
                    cur->right = new Node(x);
                    break;
                }
                cur = cur->right;
            }
        }
        for (size_t j = 0; j < path.size(); ++j) {
            if (j) cout << " ";
            cout << path[j];
        }
        cout << "\n";
    }
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.