首页 > 后端开发 > C++ > 正文

将给定二叉搜索树中的所有较大值添加到每个节点上

WBOY
发布: 2023-09-07 12:17:04
转载
1280 人浏览过

将给定二叉搜索树中的所有较大值添加到每个节点上

BST或二叉搜索树是一种二叉树形式,其中所有左节点的值小于根节点的值,所有右节点的值大于根节点的值。对于这个问题,我们将取一个二叉树并将所有大于当前节点值的值添加到它中。问题“向BST的每个节点添加所有较大的值”被简化为对于BST,将所有大于当前节点值的节点值添加到该节点值。

向BST中的每个节点添加所有较大的值问题陈述:

给定一个二叉搜索树(BST),我们需要为每个节点添加所有较大值节点的总和。

输入

    10
    /  \
   /    \
  5     20
 / \   / \
1   7   1  5
登录后复制

输出

      70
    /   \
   82   45
  / \   / \
83 77  60 25
登录后复制

解释

这个程序将把一个二叉搜索树转换为一个二叉树,其中节点的值为所有较大元素的和加上节点的原始值。

将所有较大的值添加到二叉搜索树解决方案中的每个节点:

我们使用逆向中序遍历(先递归调用右子树而不是左子树),并维护一个变量来存储到目前为止已经遍历过的节点的和。

然后,我们使用这个和来修改当前节点的值,首先将其值加到和上,然后用这个和替换节点的值。

示例

#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;
}
登录后复制

以上是将给定二叉搜索树中的所有较大值添加到每个节点上的详细内容。更多信息请关注PHP中文网其他相关文章!

相关标签:
来源:tutorialspoint.com
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责声明 Sitemap
PHP中文网:公益在线PHP培训,帮助PHP学习者快速成长!