在 C++ 中将 BST 转换为二叉树，以便将所有较大键的总和添加到每个键中
c++server side programmingprogramming
在本教程中，我们将讨论一个将 BST 转换为二叉树的程序 以便将所有较大键的总和添加到每个键中。
为此，我们将提供一个二叉搜索树。我们的任务是将该树转换为二叉树，并将所有较大键的总和添加到当前键中。这将通过按给定 BST 的顺序反转以及获取所有先前元素的总和并最终将其添加到当前元素来完成。
示例
#include <bits/stdc++.h>
using namespace std;
//BST 的节点结构
struct node{
int key;
struct node* left;
struct node* right;
};
//创建没有子节点的新节点
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);
}
//按逆序遍历 BST 并添加总和
void reverse_BST(struct node *root, int *sum_ptr){
if (root == NULL)
return;
reverse_BST(root->right, sum_ptr);
//沿途添加元素
*sum_ptr = *sum_ptr + root->key;
root->key = *sum_ptr;
reverse_BST(root->left, sum_ptr);
}
//使用 sum 并更新值
void change_greater(struct node *root){
int sum = 0;
reverse_BST(root, &sum);
}
//打印中序遍历
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 << "给定树 :" << endl;
printInorder(root);
change_greater(root);
cout << endl;
cout << "修改后的树:<< endl;
printInorder(root);
return 0;
}
输出
给定树: 2 5 13 修改后的树: 20 18 13
