Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để chuyển đổi một BST thành một cây nhị phân, trong đó tổng của tất cả các khóa lớn hơn được thêm vào mỗi khóa.
Đối với điều này, chúng tôi sẽ được cung cấp một cây Tìm kiếm nhị phân. Nhiệm vụ của chúng ta là chuyển cây đó thành cây nhị phân với tổng của tất cả các khóa lớn hơn được thêm vào khóa hiện tại. Điều này sẽ được thực hiện ngược lại theo thứ tự của BST đã cho cùng với việc có tổng của tất cả các phần tử trước đó và cuối cùng thêm nó vào phần tử hiện tại.
Ví dụ
#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;
} Đầu ra
Given Tree : 2 5 13 Modified Tree : 20 18 13