เพิ่มค่าที่มากกว่าทุกค่าไปยังทุกโหนดใน BST ที่กำหนด

นี่คือปัญหาที่น่าสนใจหนึ่งปัญหา ซึ่งเราจะเพิ่มค่าที่มากกว่าค่าของโหนดปัจจุบันไปยังโหนดนั้นๆ ในต้นไม้ค้นหาแบบทวิภาค (BST) ที่กำหนด ต้นไม้เริ่มต้นและต้นไม้สุดท้ายจะมีลักษณะดังภาพด้านล่าง

อัลกอริทึม

bstUpdate(root, sum) -

Begin
    if root is null, then stop
    bstUpdate(right of root, sum)
    sum := sum + value of root
    update root value using sum
    bstUpdate(left of root, sum)
End

ตัวอย่าง

#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); // อัปเดต subtree ขวา
    *sum = *sum + root->data;
    root->data = *sum; // อัปเดตข้อมูลราก
    updateBST(root->left, sum); // อัปเดต subtree ซ้าย
}
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) // ไปทางซ้าย
        node->left = insert(node->left, data);
    else // ไปทางขวา
        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);
}

ผลลัพธ์

350 330 300 260 210 150 80