数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学在 C++ 中将所有大于节点的值添加到给定 BST 的每个节点？
BST 或二叉搜索树是一种二叉树，其所有左子节点都小于根值，所有右子节点都大于根值。对于这个问题，我们将采用二叉树并将所有大于当前节点的值添加到其中。“将所有大于节点的值添加到 BST 的每个节点中”这个问题简化为：对于 BST，将所有大于当前节点值的值添加到该节点值中。
将所有大于节点的值添加到 BST 中的每个节点中 问题陈述 -
给定一个二叉搜索树 (BST)，我们需要为每个节点添加所有大于该节点的值的总和。
说明
此程序将把 BST 转换为二叉树，其节点值为所有大于元素的总和加上节点的原始值。
将所有大于节点的值添加到二叉搜索树中的每个节点中的解决方案 -
我们使用反向中序遍历（递归首先调用右子树而不是左子树）并维护一个变量来存储到目前为止已遍历的节点的总和。
然后，我们使用此总和来修改当前节点的值，首先将其值添加到总和中，然后用此总和替换节点的值。
示例
#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;
}
更新于： 2019年10月24日
82 次查看
广告