Chuyển BST thường thành BST cân bằng trong C++

Chuyển cây tìm kiếm nhị phân (BST) lệch (skewed) thành BST cân bằng (balanced BST).

Thuật toán

1. Duyệt inorder BST gốc → lưu con trỏ nút vào vector (đã sắp xếp)
2. Xây dựng BST cân bằng từ vector: chọn phần tử giữa làm gốc, đệ quy xây trái/phải

Chương trình C++

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

struct Node {
    int data;
    Node* left, *right;
};

void store_nodes(Node* root, vector<Node*> &nodes) {
    if (root == NULL) return;
    store_nodes(root->left, nodes);
    nodes.push_back(root);
    store_nodes(root->right, nodes);
}

Node* construct_tree(vector<Node*> &nodes, int start, int end) {
    if (start > end) return NULL;
    int mid = (start + end) / 2;
    Node *root = nodes[mid];
    root->left = construct_tree(nodes, start, mid - 1);
    root->right = construct_tree(nodes, mid + 1, end);
    return root;
}

Node* buildTree(Node* root) {
    vector<Node*> nodes;
    store_nodes(root, nodes);
    int n = nodes.size();
    return construct_tree(nodes, 0, n - 1);
}

Node* newNode(int data) {
    Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

void preOrder(Node* node) {
    if (node == NULL) return;
    printf("%d ", node->data);
    preOrder(node->left);
    preOrder(node->right);
}

int main() {
    Node* root = newNode(10);
    root->left = newNode(8);
    root->left->left = newNode(7);
    root->left->left->left = newNode(6);
    root->left->left->left->left = newNode(5);
    root = buildTree(root);
    printf("Preorder traversal of balanced BST:\n");
    preOrder(root);
    return 0;
}

Kết quả

Preorder traversal of balanced BST: 7 5 6 8 10

Giải thích

BST gốc: 5-6-7-8-10 (chỉ nhánh trái). BST cân bằng: gốc 7, trái 5-6, phải 8-10. Độ cao giảm từ 4 xuống 2.