BST หรือแผนผังการค้นหาแบบไบนารีคือรูปแบบของไบนารีทรีที่มีโหนดด้านซ้ายทั้งหมดที่มีขนาดเล็กกว่าและโหนดด้านขวาทั้งหมดมีค่ามากกว่าค่ารูท สำหรับปัญหานี้ เราจะนำไบนารีทรีและเพิ่มค่าทั้งหมดที่มากกว่าโหนดปัจจุบันเข้าไป ปัญหา “เพิ่มค่าที่มากกว่าทั้งหมดให้กับทุกโหนดใน BST” นั้นง่ายขึ้น สำหรับ BST จะเพิ่มค่าโหนดทั้งหมดที่มากกว่าค่าโหนดปัจจุบันให้กับค่าโหนดนั้น
เพิ่มค่าที่มากกว่าทั้งหมดให้กับแต่ละโหนดในคำชี้แจงปัญหา BST -
จาก Binary Search Tree (BST) เราจำเป็นต้องเพิ่มไปยังแต่ละโหนด ซึ่งเป็นผลรวมของโหนดที่มีค่ามากกว่าทั้งหมด
คำอธิบาย
โปรแกรมนี้จะแปลง BST เป็นไบนารีทรีด้วยค่าของโหนดเป็นผลรวมขององค์ประกอบที่มากกว่าทั้งหมดบวกกับค่าเดิมของโหนด
เพิ่มค่าที่มากกว่าทั้งหมดให้กับแต่ละโหนดในโซลูชัน Binary Search Tree -
เราใช้ Reverse Inorder Traversal (เรียกซ้ำบนทรีย่อยด้านขวาก่อน แทนที่จะเป็นทรีย่อยด้านซ้าย) และรักษาตัวแปรเพื่อเก็บผลรวมของโหนดที่ข้ามผ่านมาแล้ว
จากนั้นเราใช้ผลรวมนี้เพื่อแก้ไขค่าของโหนดปัจจุบัน โดยเพิ่มมูลค่าลงในผลรวมก่อน จากนั้นจึงแทนที่ค่าของโหนดด้วยผลรวมนี้
ตัวอย่าง
#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;
} 