Dado un árbol de búsqueda binario ( BST ), modifíquelo para que todos los valores mayores en el BST dado se agreguen a cada Node. Por ejemplo, considere el siguiente BST.
50
/ \
30 70
/ \ / \
20 40 60 80
The above tree should be modified to following
260
/ \
330 150
/ \ / \
350 300 210 80
Un método simple para resolver esto es encontrar la suma de todos los valores mayores para cada Node. Este método tomaría O (n ^ 2) tiempo.
C++
// C++ program to add all greater
// values in every node of BST
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
};
// A utility function to create
// a new BST node
Node* newNode(int item)
{
Node* temp = new Node();
temp->data = item;
temp->left = temp->right = NULL;
return temp;
}
// Recursive function to add all
// greater values in every node
void modifyBSTUtil(Node* root, int* sum)
{
// Base Case
if (root == NULL)
return;
// Recur for right subtree
modifyBSTUtil(root->right, sum);
// Now *sum has sum of nodes
// in right subtree, add
// root->data to sum and
// update root->data
*sum = *sum + root->data;
root->data = *sum;
// Recur for left subtree
modifyBSTUtil(root->left, sum);
}
// A wrapper over modifyBSTUtil()
void modifyBST(Node* root)
{
int sum = 0;
modifyBSTUtil(root, &sum);
}
// A utility function to do
// inorder traversal of BST
void inorder(Node* root)
{
if (root != NULL) {
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
}
/* A utility function to insert
a new node with given data in BST */
Node* insert(Node* node, int data)
{
/* If the tree is empty,
return a new node */
if (node == NULL)
return newNode(data);
/* Otherwise, recur down the tree */
if (data <= node->data)
node->left = insert(node->left, data);
else
node->right = insert(node->right, data);
/* return the (unchanged) node pointer */
return node;
}
// Driver code
int main()
{
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
Node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
modifyBST(root);
// print inorder traversal of the modified BST
inorder(root);
return 0;
}
// This code is contributed by rathbhupendra
C
// C program to add all greater
// values in every node of BST
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *left, *right;
};
// A utility function to create a new BST node
struct Node* newNode(int item)
{
struct Node* temp
= (struct Node*)malloc(
sizeof(struct Node));
temp->data = item;
temp->left = temp->right = NULL;
return temp;
}
// Recursive function to add
// all greater values in every node
void modifyBSTUtil(
struct Node* root, int* sum)
{
// Base Case
if (root == NULL)
return;
// Recur for right subtree
modifyBSTUtil(root->right, sum);
// Now *sum has sum of nodes
// in right subtree, add
// root->data to sum and
// update root->data
*sum = *sum + root->data;
root->data = *sum;
// Recur for left subtree
modifyBSTUtil(root->left, sum);
}
// A wrapper over modifyBSTUtil()
void modifyBST(struct Node* root)
{
int sum = 0;
modifyBSTUtil(root, &sum);
}
// A utility function to do
// inorder traversal of BST
void inorder(struct Node* root)
{
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
/* A utility function to insert
a new node with given data in BST */
struct Node* insert(
struct Node* node, int data)
{
/* If the tree is empty, return a new node */
if (node == NULL)
return newNode(data);
/* Otherwise, recur down the tree */
if (data <= node->data)
node->left = insert(node->left, data);
else
node->right = insert(node->right, data);
/* return the (unchanged) node pointer */
return node;
}
// Driver Program to test above functions
int main()
{
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
struct Node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
modifyBST(root);
// print inorder traversal of the modified BST
inorder(root);
return 0;
}
Java
// Java code to add all greater values to
// every node in a given BST
// A binary tree node
class Node {
int data;
Node left, right;
Node(int d)
{
data = d;
left = right = null;
}
}
class BinarySearchTree {
// Root of BST
Node root;
// Constructor
BinarySearchTree()
{
root = null;
}
// Inorder traversal of the tree
void inorder()
{
inorderUtil(this.root);
}
// Utility function for inorder traversal of
// the tree
void inorderUtil(Node node)
{
if (node == null)
return;
inorderUtil(node.left);
System.out.print(node.data + " ");
inorderUtil(node.right);
}
// adding new node
public void insert(int data)
{
this.root = this.insertRec(this.root, data);
}
/* A utility function to insert a new node with
given data in BST */
Node insertRec(Node node, int data)
{
/* If the tree is empty, return a new node */
if (node == null) {
this.root = new Node(data);
return this.root;
}
/* Otherwise, recur down the tree */
if (data <= node.data) {
node.left = this.insertRec(node.left, data);
}
else {
node.right = this.insertRec(node.right, data);
}
return node;
}
// This class initialises the value of sum to 0
public class Sum {
int sum = 0;
}
// Recursive function to add all greater values in
// every node
void modifyBSTUtil(Node node, Sum S)
{
// Base Case
if (node == null)
return;
// Recur for right subtree
this.modifyBSTUtil(node.right, S);
// Now *sum has sum of nodes in right subtree, add
// root->data to sum and update root->data
S.sum = S.sum + node.data;
node.data = S.sum;
// Recur for left subtree
this.modifyBSTUtil(node.left, S);
}
// A wrapper over modifyBSTUtil()
void modifyBST(Node node)
{
Sum S = new Sum();
this.modifyBSTUtil(node, S);
}
// Driver Function
public static void main(String[] args)
{
BinarySearchTree tree = new BinarySearchTree();
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
tree.modifyBST(tree.root);
// print inorder traversal of the modified BST
tree.inorder();
}
}
// This code is contributed by Kamal Rawal
Python3
# Python3 program to add all greater values # in every node of BST # A utility function to create a # new BST node class newNode: # Constructor to create a new node def __init__(self, data): self.data = data self.left = None self.right = None # Recursive function to add all greater # values in every node def modifyBSTUtil(root, Sum): # Base Case if root == None: return # Recur for right subtree modifyBSTUtil(root.right, Sum) # Now Sum[0] has sum of nodes in right # subtree, add root.data to sum and # update root.data Sum[0] = Sum[0] + root.data root.data = Sum[0] # Recur for left subtree modifyBSTUtil(root.left, Sum) # A wrapper over modifyBSTUtil() def modifyBST(root): Sum = [0] modifyBSTUtil(root, Sum) # A utility function to do inorder # traversal of BST def inorder(root): if root != None: inorder(root.left) print(root.data, end =" ") inorder(root.right) # A utility function to insert a new node # with given data in BST def insert(node, data): # If the tree is empty, return a new node if node == None: return newNode(data) # Otherwise, recur down the tree if data <= node.data: node.left = insert(node.left, data) else: node.right = insert(node.right, data) # return the (unchanged) node pointer return node # Driver Code if __name__ == '__main__': # Let us create following BST # 50 # / \ # 30 70 # / \ / \ # 20 40 60 80 root = None root = insert(root, 50) insert(root, 30) insert(root, 20) insert(root, 40) insert(root, 70) insert(root, 60) insert(root, 80) modifyBST(root) # print inorder traversal of the # modified BST inorder(root) # This code is contributed by PranchalK
C#
using System;
// C# code to add all greater values to
// every node in a given BST
// A binary tree node
public class Node {
public int data;
public Node left, right;
public Node(int d)
{
data = d;
left = right = null;
}
}
public class BinarySearchTree {
// Root of BST
public Node root;
// Constructor
public BinarySearchTree()
{
root = null;
}
// Inorder traversal of the tree
public virtual void inorder()
{
inorderUtil(this.root);
}
// Utility function for inorder traversal of
// the tree
public virtual void inorderUtil(Node node)
{
if (node == null) {
return;
}
inorderUtil(node.left);
Console.Write(node.data + " ");
inorderUtil(node.right);
}
// adding new node
public virtual void insert(int data)
{
this.root = this.insertRec(this.root, data);
}
/* A utility function to insert a new node with
given data in BST */
public virtual Node insertRec(Node node, int data)
{
/* If the tree is empty, return a new node */
if (node == null) {
this.root = new Node(data);
return this.root;
}
/* Otherwise, recur down the tree */
if (data <= node.data) {
node.left = this.insertRec(node.left, data);
}
else {
node.right = this.insertRec(node.right, data);
}
return node;
}
// This class initialises the value of sum to 0
public class Sum {
private readonly BinarySearchTree outerInstance;
public Sum(BinarySearchTree outerInstance)
{
this.outerInstance = outerInstance;
}
public int sum = 0;
}
// Recursive function to add all greater values in
// every node
public virtual void modifyBSTUtil(Node node, Sum S)
{
// Base Case
if (node == null) {
return;
}
// Recur for right subtree
this.modifyBSTUtil(node.right, S);
// Now *sum has sum of nodes in right subtree, add
// root->data to sum and update root->data
S.sum = S.sum + node.data;
node.data = S.sum;
// Recur for left subtree
this.modifyBSTUtil(node.left, S);
}
// A wrapper over modifyBSTUtil()
public virtual void modifyBST(Node node)
{
Sum S = new Sum(this);
this.modifyBSTUtil(node, S);
}
// Driver Function
public static void Main(string[] args)
{
BinarySearchTree tree = new BinarySearchTree();
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
tree.modifyBST(tree.root);
// print inorder traversal of the modified BST
tree.inorder();
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// JavaScript code to add all greater values to
// every node in a given BST
// A binary tree node
class Node {
constructor(val) {
this.data = val;
this.left = null;
this.right = null;
}
}
// Root of BST
var root = null;
// Inorder traversal of the tree
function inorder()
{
inorderUtil(this.root);
}
// Utility function for inorder traversal of
// the tree
function inorderUtil(node)
{
if (node == null)
return;
inorderUtil(node.left);
document.write(node.data + " ");
inorderUtil(node.right);
}
// adding new node
function insert(data)
{
this.root = this.insertRec(this.root, data);
}
/* A utility function to insert a new node with
given data in BST */
function insertRec(node , data)
{
/* If the tree is empty, return a new node */
if (node == null) {
this.root = new Node(data);
return this.root;
}
/* Otherwise, recur down the tree */
if (data <= node.data) {
node.left = this.insertRec(node.left, data);
}
else {
node.right = this.insertRec(node.right, data);
}
return node;
}
// This class initialises the value of sum to 0
class Sum {
constructor(){
this.sum = 0;
}
}
// Recursive function to add
// all greater values in
// every node
function modifyBSTUtil(node, S)
{
// Base Case
if (node == null)
return;
// Recur for right subtree
this.modifyBSTUtil(node.right, S);
// Now *sum has sum of nodes
// in right subtree, add
// root->data to sum and update root->data
S.sum = S.sum + node.data;
node.data = S.sum;
// Recur for left subtree
this.modifyBSTUtil(node.left, S);
}
// A wrapper over modifyBSTUtil()
function modifyBST(node)
{
var S = new Sum();
this.modifyBSTUtil(node, S);
}
// Driver Function
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
insert(50);
insert(30);
insert(20);
insert(40);
insert(70);
insert(60);
insert(80);
modifyBST(root);
// print inorder traversal of the modified BST
inorder();
// This code contributed by gauravrajput1
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA