Chuyển đổi cây BST thành cây nhị phân với tổng các khóa lớn hơn được cộng vào mỗi khóa trong C++

Trong hướng dẫn này, chúng ta sẽ chuyển đổi một cây tìm kiếm nhị phân (BST) thành một cây nhị phân sao cho mỗi nút chứa giá trị gốc cộng với tổng của tất cả các khóa lớn hơn nó trong BST.

Ý tưởng: Duyệt BST theo thứ tự trung tự ngược (reverse inorder: phải - gốc - trái). Khi duyệt, ta duy trì một biến tổng tích lũy. Tại mỗi nút, cộng giá trị nút vào tổng, sau đó cập nhật giá trị nút bằng tổng hiện tại.

Ví dụ minh họa (C++)

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

struct Node {
    int key;
    Node* left;
    Node* right;
};

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

// Duyệt reverse inorder và cập nhật tổng
void reverse_BST(Node* root, int* sum_ptr) {
    if (root == nullptr) return;
    reverse_BST(root->right, sum_ptr);   // Duyệt cây con phải trước
    *sum_ptr += root->key;               // Cộng giá trị hiện tại vào tổng
    root->key = *sum_ptr;                // Cập nhật giá trị nút = tổng tích lũy
    reverse_BST(root->left, sum_ptr);    // Duyệt cây con trái
}

void change_greater(Node* root) {
    int sum = 0;
    reverse_BST(root, &sum);
}

// In inorder để kiểm tra
void printInorder(Node* node) {
    if (node == nullptr) return;
    printInorder(node->left);
    cout << node->key << " ";
    printInorder(node->right);
}

int main() {
    Node* root = newNode(5);
    root->left = newNode(2);
    root->right = newNode(13);
    cout << "Cay goc (inorder): ";
    printInorder(root);
    change_greater(root);
    cout << "\nCay sau khi chuyen doi (inorder): ";
    printInorder(root);
    return 0;
}

Kết quả

Cay goc (inorder): 2 5 13
Cay sau khi chuyen doi (inorder): 20 18 13

Giải thích: Nút 13 (lớn nhất) giữ nguyên 13. Nút 5 trở thành 5+13=18. Nút 2 trở thành 2+5+13=20.