ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมที่จะแปลง BST เป็นไบนารีทรีเพื่อให้ผลรวมของคีย์ที่มากกว่าทั้งหมดถูกรวมเข้ากับทุกคีย์
สำหรับสิ่งนี้ เราจะได้รับ Binary Search tree งานของเราคือการแปลงทรีนั้นเป็นไบนารีทรีโดยมีผลรวมของคีย์ที่มากกว่าทั้งหมดที่เพิ่มเข้าไปในคีย์ปัจจุบัน สิ่งนี้จะทำโดยการย้อนกลับตามลำดับของ BST ที่กำหนดพร้อมกับผลรวมขององค์ประกอบก่อนหน้าทั้งหมดและสุดท้ายเพิ่มลงในองค์ประกอบปัจจุบัน
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
//node structure of BST
struct node{
int key;
struct node* left;
struct node* right;
};
//creating new node with no child
struct node* newNode(int key){
struct node* node = (struct node*)malloc(sizeof(struct node));
node->key = key;
node->left = NULL;
node->right = NULL;
return (node);
}
//traversing BST in reverse inorder and adding sum
void reverse_BST(struct node *root, int *sum_ptr){
if (root == NULL)
return;
reverse_BST(root->right, sum_ptr);
//adding elements along the way
*sum_ptr = *sum_ptr + root->key;
root->key = *sum_ptr;
reverse_BST(root->left, sum_ptr);
}
//Using sum and updating the values
void change_greater(struct node *root){
int sum = 0;
reverse_BST(root, &sum);
}
//printing inorder traversal
void printInorder(struct node* node){
if (node == NULL)
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 << "Given Tree :" << endl;
printInorder(root);
change_greater(root);
cout << endl;
cout << "Modified Tree :" << endl;
printInorder(root);
return 0;
} ผลลัพธ์
Given Tree : 2 5 13 Modified Tree : 20 18 13
