Chuyển cây nhị phân sang cây tìm kiếm nhị phân C++

Chuyển cây nhị phân (BT) sang cây tìm kiếm nhị phân (BST) giữ nguyên cấu trúc. BT: mỗi nút tối đa 2 con. BST: trái < gốc < phải, cả hai cây con cũng là BST.

3 bước: In-order → Sort → In-order fill

1. Duyệt in-order BT, lưu giá trị vào mảng.
2. Sắp xếp mảng.
3. Duyệt in-order BT lần 2, gán giá trị từ mảng đã sort.

Ví dụ minh họa

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

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

void inorderStore(Node* root, vector& arr) {
    if (!root) return;
    inorderStore(root->left, arr);
    arr.push_back(root->data);
    inorderStore(root->right, arr);
}

void inorderFill(Node* root, vector& arr, int& idx) {
    if (!root) return;
    inorderFill(root->left, arr, idx);
    root->data = arr[idx++];
    inorderFill(root->right, arr, idx);
}

Node* newNode(int d) {
    Node* n = new Node();
    n->data = d; n->left = n->right = nullptr;
    return n;
}

void printInorder(Node* root) {
    if (!root) return;
    printInorder(root->left);
    cout << root->data << ' ';
    printInorder(root->right);
}

int main() {
    Node* root = newNode(17);
    root->left = newNode(14);
    root->right = newNode(2);
    root->left->left = newNode(11);
    root->right->right = newNode(7);
    
    cout << "Inorder BT: "; printInorder(root); cout << '\n';
    
    vector arr;
    inorderStore(root, arr);
    sort(arr.begin(), arr.end());
    int idx = 0;
    inorderFill(root, arr, idx);
    
    cout << "Inorder BST: "; printInorder(root);
    return 0;
}

Kết quả

Inorder BT: 11 14 17 2 7
Inorder BST: 2 7 11 14 17