Thêm tất cả giá trị lớn hơn vào mỗi nút trong BST cho trước

Chúng ta sẽ xem xét một bài toán thú vị: cộng các giá trị lớn hơn vào mỗi nút của một cây tìm kiếm nhị phân (BST) cho trước. Cây ban đầu và cây sau khi xử lý sẽ trông như sau:

Thuật toán

bstUpdate(root, sum) -

Bắt đầu
    nếu root là null, thì dừng
    bstUpdate(cây con phải của root, sum)
    sum := sum + giá trị của root
    cập nhật giá trị root bằng sum
    bstUpdate(cây con trái của root, sum)
Kết thúc

Ví dụ

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node *left, *right;
};

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

void updateBST(Node *root, int *sum) {
    if (root == NULL)
        return;
    updateBST(root->right, sum); // cập nhật cây con phải
    *sum = *sum + root->data;
    root->data = *sum; // cập nhật dữ liệu root
    updateBST(root->left, sum); // cập nhật cây con trái
}

void BSTUpdate(Node *root) {
    int sum = 0;
    updateBST(root, &sum);
}

void inorder(Node *root) {
    if (root != NULL) {
        inorder(root->left);
        cout << root->data << " ";
        inorder(root->right);
    }
}

Node* insert(Node* node, int data) {
    if (node == NULL)
        return getNode(data);
    if (data <= node->data) // đi sang trái
        node->left = insert(node->left, data);
    else // đi sang phải
        node->right = insert(node->right, data);
    return node;
}

int main() {
    int data[] = {50, 30, 20, 40, 70, 60, 80};
    int n = sizeof(data)/sizeof(data[0]);
    Node *root = NULL;
    for(int i = 0; i < n; i++) {
        root = insert(root, data[i]);
    }
    BSTUpdate(root);
    inorder(root);
}

Kết quả

350 330 300 260 210 150 80