BST (Binary Search Tree) เป็นต้นไม้ทวิภาคที่โหนดซ้ายทั้งหมดมีค่าน้อยกว่าราก และโหนดขวาทั้งหมดมีค่ามากกว่าราก สำหรับปัญหานี้ เราจะนำต้นไม้ทวิภาคมาและบวกค่าของโหนดที่มากกว่าโหนดปัจจุบันทั้งหมดเข้าไปในโหนดนั้น ปัญหา "เพิ่มค่าที่มากกว่าทุกค่าไปยังทุกโหนดใน BST" สามารถลดรูปได้ว่า สำหรับ BST ให้บวกค่าของโหนดที่มากกว่าค่าโหนดปัจจุบันเข้าไปในโหนดนั้น
โจทย์: เพิ่มค่าที่มากกว่าไปยังแต่ละโหนดใน BST
ข้อมูลเข้า
10
/ \
5 20
/ \ / \
1 7 15 25ข้อมูลออก
70
/ \
82 45
/ \ / \
83 77 60 25คำอธิบาย
โปรแกรมนี้จะแปลง BST ให้กลายเป็น Binary Tree ที่ค่าโหนดแต่ละตัวเป็นผลรวมของค่าที่มากกว่าทั้งหมดบวกกับค่าเดิมของโหนด
วิธีแก้: เพิ่มค่าที่มากกว่าไปยังแต่ละโหนดใน Binary Search Tree
เราใช้ Reverse Inorder Traversal (เรียก Recursive บน Subtree ขวาก่อน Subtree ซ้าย) และเก็บตัวแปร Sum สำหรับผลรวมของโหนดที่ผ่านมาแล้ว
จากนั้นใช้ Sum นี้ปรับค่าโหนดปัจจุบัน โดยบวกค่าโหนดเข้า Sum ก่อน แล้วแทนที่ค่าโหนดด้วย Sum นี้
ตัวอย่าง
#include <iostream >
using namespace std;
struct node {
int data;
node *left;
node *right;
};
node *newNode(int key) {
node *temp = new node;
temp->left = NULL;
temp->right = NULL;
temp->data = key;
return temp;
}
void Inorder(node *root) {
if(!root)
return;
Inorder(root->left);
cout << root->data << " ";
Inorder(root->right);
}
node *Insert(node *root, int key) {
if(!root)
return newNode(key);
if(key < root->data)
root->left = Insert(root->left, key);
else
root->right = Insert(root->right, key);
return root;
}
void RevInorderAdd(node *root, int &sum) {
if(!root)
return;
RevInorderAdd(root->right, sum);
sum += root->data;
root->data = sum;
RevInorderAdd(root->left, sum);
}
void AddGreater(node *root) {
int sum = 0;
RevInorderAdd(root, sum);
}
int main() {
/* Let us create following BST
10
/ \
5 20
/ \ / \
1 7 15 25 */
node *root = NULL;
root = Insert(root, 10);
Insert(root, 20);
Insert(root, 25);
Insert(root, 15);
Insert(root, 5);
Insert(root, 7);
Insert(root, 1);
Inorder(root);
cout << endl;
AddGreater(root);
Inorder(root);
cout << endl;
return 0;
}