Pregunta: Dado un árbol binario arbitrario, conviértalo en un árbol binario que contenga Children Sum Property . Solo puede incrementar los valores de datos en cualquier Node (no puede cambiar la estructura del árbol y no puede disminuir el valor de ningún Node).
Por ejemplo, el siguiente árbol no contiene la propiedad de suma de niños, conviértalo en un árbol que contenga la propiedad.
50
/ \
/ \
7 2
/ \ /\
/ \ / \
3 5 1 30
Algoritmo: Atraviese el árbol dado en orden posterior para convertirlo, es decir, primero cambie los elementos secundarios izquierdo y derecho para mantener la propiedad sum de los elementos secundarios y luego cambie el Node principal.
Deje que la diferencia entre los datos del Node y la suma de los niños sea diferente.
C++
/* C++ Program to convert an arbitrary
binary tree to a tree that hold
children sum property */
#include<bits/stdc++.h>
using namespace std;
class node
{
public:
int data;
node* left;
node* right;
/* Constructor that allocates a new node
with the given data and NULL left and right
pointers. */
node(int data)
{
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
/* This function is used
to increment left subtree */
void increment(node* node, int diff);
/* This function changes a tree
to hold children sum property */
void convertTree(node* node)
{
int left_data = 0, right_data = 0, diff;
/* If tree is empty or it's a leaf
node then return true */
if (node == NULL || (node->left == NULL &&
node->right == NULL))
return;
else
{
/* convert left and right subtrees */
convertTree(node->left);
convertTree(node->right);
/* If left child is not present then 0 is used
as data of left child */
if (node->left != NULL)
left_data = node->left->data;
/* If right child is not present then 0 is used
as data of right child */
if (node->right != NULL)
right_data = node->right->data;
/* get the diff of node's data and children sum */
diff = left_data + right_data - node->data;
/* If node's children sum is
greater than the node's data */
if (diff > 0)
node->data = node->data + diff;
/* THIS IS TRICKY --> If node's data
is greater than children sum,
then increment subtree by diff */
if (diff < 0)
increment(node, -diff); // -diff is used to make diff positive
}
}
/* This function is used
to increment subtree by diff */
void increment(node* node, int diff)
{
/* IF left child is not
NULL then increment it */
if(node->left != NULL)
{
node->left->data = node->left->data + diff;
// Recursively call to fix
// the descendants of node->left
increment(node->left, diff);
}
else if (node->right != NULL) // Else increment right child
{
node->right->data = node->right->data + diff;
// Recursively call to fix
// the descendants of node->right
increment(node->right, diff);
}
}
/* Given a binary tree,
printInorder() prints out its
inorder traversal*/
void printInorder(node* node)
{
if (node == NULL)
return;
/* first recur on left child */
printInorder(node->left);
/* then print the data of node */
cout<<node->data<<" ";
/* now recur on right child */
printInorder(node->right);
}
/* Driver code */
int main()
{
node *root = new node(50);
root->left = new node(7);
root->right = new node(2);
root->left->left = new node(3);
root->left->right = new node(5);
root->right->left = new node(1);
root->right->right = new node(30);
cout << "\nInorder traversal before conversion: " << endl;
printInorder(root);
convertTree(root);
cout << "\nInorder traversal after conversion: " << endl;
printInorder(root);
return 0;
}
// This code is contributed by rathbhupendra
C
/* Program to convert an arbitrary binary tree to
a tree that holds children sum property */
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node* left;
struct node* right;
};
/* This function is used to increment left subtree */
void increment(struct node* node, int diff);
/* Helper function that allocates a new node
with the given data and NULL left and right
pointers. */
struct node* newNode(int data);
/* This function changes a tree to hold children sum
property */
void convertTree(struct node* node)
{
int left_data = 0, right_data = 0, diff;
/* If tree is empty or it's a leaf node then
return true */
if (node == NULL ||
(node->left == NULL && node->right == NULL))
return;
else
{
/* convert left and right subtrees */
convertTree(node->left);
convertTree(node->right);
/* If left child is not present then 0 is used
as data of left child */
if (node->left != NULL)
left_data = node->left->data;
/* If right child is not present then 0 is used
as data of right child */
if (node->right != NULL)
right_data = node->right->data;
/* get the diff of node's data and children sum */
diff = left_data + right_data - node->data;
/* If node's children sum is greater than the node's data */
if (diff > 0)
node->data = node->data + diff;
/* THIS IS TRICKY --> If node's data is greater than children sum,
then increment subtree by diff */
if (diff < 0)
increment(node, -diff); // -diff is used to make diff positive
}
}
/* This function is used to increment subtree by diff */
void increment(struct node* node, int diff)
{
/* IF left child is not NULL then increment it */
if(node->left != NULL)
{
node->left->data = node->left->data + diff;
// Recursively call to fix the descendants of node->left
increment(node->left, diff);
}
else if (node->right != NULL) // Else increment right child
{
node->right->data = node->right->data + diff;
// Recursively call to fix the descendants of node->right
increment(node->right, diff);
}
}
/* Given a binary tree, printInorder() prints out its
inorder traversal*/
void printInorder(struct node* node)
{
if (node == NULL)
return;
/* first recur on left child */
printInorder(node->left);
/* then print the data of node */
printf("%d ", node->data);
/* now recur on right child */
printInorder(node->right);
}
/* Helper function that allocates a new node
with the given data and NULL left and right
pointers. */
struct node* newNode(int data)
{
struct node* node =
(struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/* Driver program to test above functions */
int main()
{
struct node *root = newNode(50);
root->left = newNode(7);
root->right = newNode(2);
root->left->left = newNode(3);
root->left->right = newNode(5);
root->right->left = newNode(1);
root->right->right = newNode(30);
printf("\n Inorder traversal before conversion ");
printInorder(root);
convertTree(root);
printf("\n Inorder traversal after conversion ");
printInorder(root);
getchar();
return 0;
}
Java
// Java program to convert an arbitrary binary tree to a tree that holds
// children sum property
// A binary tree node
class Node
{
int data;
Node left, right;
Node(int item)
{
data = item;
left = right = null;
}
}
class BinaryTree
{
Node root;
/* This function changes a tree to hold children sum
property */
void convertTree(Node node)
{
int left_data = 0, right_data = 0, diff;
/* If tree is empty or it's a leaf node then
return true */
if (node == null
|| (node.left == null && node.right == null))
return;
else
{
/* convert left and right subtrees */
convertTree(node.left);
convertTree(node.right);
/* If left child is not present then 0 is used
as data of left child */
if (node.left != null)
left_data = node.left.data;
/* If right child is not present then 0 is used
as data of right child */
if (node.right != null)
right_data = node.right.data;
/* get the diff of node's data and children sum */
diff = left_data + right_data - node.data;
/* If node's children sum is greater than the node's data */
if (diff > 0)
node.data = node.data + diff;
/* THIS IS TRICKY --> If node's data is greater than children
sum, then increment subtree by diff */
if (diff < 0)
// -diff is used to make diff positive
increment(node, -diff);
}
}
/* This function is used to increment subtree by diff */
void increment(Node node, int diff)
{
/* IF left child is not NULL then increment it */
if (node.left != null)
{
node.left.data = node.left.data + diff;
// Recursively call to fix the descendants of node->left
increment(node.left, diff);
}
else if (node.right != null) // Else increment right child
{
node.right.data = node.right.data + diff;
// Recursively call to fix the descendants of node->right
increment(node.right, diff);
}
}
/* Given a binary tree, printInorder() prints out its
inorder traversal*/
void printInorder(Node node)
{
if (node == null)
return;
/* first recur on left child */
printInorder(node.left);
/* then print the data of node */
System.out.print(node.data + " ");
/* now recur on right child */
printInorder(node.right);
}
// Driver program to test above functions
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(50);
tree.root.left = new Node(7);
tree.root.right = new Node(2);
tree.root.left.left = new Node(3);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(1);
tree.root.right.right = new Node(30);
System.out.println("Inorder traversal before conversion is :");
tree.printInorder(tree.root);
tree.convertTree(tree.root);
System.out.println("");
System.out.println("Inorder traversal after conversion is :");
tree.printInorder(tree.root);
}
}
// This code has been contributed by Mayank Jaiswal(mayank_24)
Python3
# Program to convert an arbitrary binary tree
# to a tree that holds children sum property
# Helper function that allocates a new
# node with the given data and None
# left and right pointers.
class newNode:
# Construct to create a new node
def __init__(self, key):
self.data = key
self.left = None
self.right = None
# This function changes a tree to
# hold children sum property
def convertTree(node):
left_data = 0
right_data = 0
diff=0
# If tree is empty or it's a
# leaf node then return true
if (node == None or (node.left == None and
node.right == None)):
return
else:
""" convert left and right subtrees """
convertTree(node.left)
convertTree(node.right)
""" If left child is not present then 0
is used as data of left child """
if (node.left != None):
left_data = node.left.data
""" If right child is not present then 0
is used as data of right child """
if (node.right != None):
right_data = node.right.data
""" get the diff of node's data
and children sum """
diff = left_data + right_data - node.data
""" If node's children sum is greater
than the node's data """
if (diff > 0):
node.data = node.data + diff
""" THIS IS TRICKY -. If node's data is
greater than children sum, then increment
subtree by diff """
if (diff < 0):
increment(node, -diff) # -diff is used to
# make diff positive
""" This function is used to increment
subtree by diff """
def increment(node, diff):
""" IF left child is not None
then increment it """
if(node.left != None):
node.left.data = node.left.data + diff
# Recursively call to fix the
# descendants of node.left
increment(node.left, diff)
elif(node.right != None): # Else increment right child
node.right.data = node.right.data + diff
# Recursively call to fix the
# descendants of node.right
increment(node.right, diff)
""" Given a binary tree, printInorder()
prints out its inorder traversal"""
def printInorder(node):
if (node == None):
return
""" first recur on left child """
printInorder(node.left)
""" then print the data of node """
print(node.data,end=" ")
""" now recur on right child """
printInorder(node.right)
# Driver Code
if __name__ == '__main__':
root = newNode(50)
root.left = newNode(7)
root.right = newNode(2)
root.left.left = newNode(3)
root.left.right = newNode(5)
root.right.left = newNode(1)
root.right.right = newNode(30)
print("Inorder traversal before conversion")
printInorder(root)
convertTree(root)
print("\nInorder traversal after conversion ")
printInorder(root)
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)
C#
// C# program to convert an arbitrary
// binary tree to a tree that holds
// children sum property
using System;
// A binary tree node
public class Node
{
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
class GFG
{
public Node root;
/* This function changes a tree to
hold children sum property */
public virtual void convertTree(Node node)
{
int left_data = 0, right_data = 0, diff;
/* If tree is empty or it's a leaf
node then return true */
if (node == null || (node.left == null &&
node.right == null))
{
return;
}
else
{
/* convert left and right subtrees */
convertTree(node.left);
convertTree(node.right);
/* If left child is not present then
0 is used as data of left child */
if (node.left != null)
{
left_data = node.left.data;
}
/* If right child is not present then
0 is used as data of right child */
if (node.right != null)
{
right_data = node.right.data;
}
/* get the diff of node's data
and children sum */
diff = left_data + right_data - node.data;
/* If node's children sum is greater
than the node's data */
if (diff > 0)
{
node.data = node.data + diff;
}
/* THIS IS TRICKY --> If node's data is
greater than children sum, then increment
subtree by diff */
if (diff < 0)
{
// -diff is used to make diff positive
increment(node, -diff);
}
}
}
/* This function is used to increment
subtree by diff */
public virtual void increment(Node node, int diff)
{
/* IF left child is not NULL then
increment it */
if (node.left != null)
{
node.left.data = node.left.data + diff;
// Recursively call to fix the
// descendants of node->left
increment(node.left, diff);
}
else if (node.right != null) // Else increment right child
{
node.right.data = node.right.data + diff;
// Recursively call to fix the
// descendants of node->right
increment(node.right, diff);
}
}
/* Given a binary tree, printInorder()
prints out its inorder traversal*/
public virtual void printInorder(Node node)
{
if (node == null)
{
return;
}
/* first recur on left child */
printInorder(node.left);
/* then print the data of node */
Console.Write(node.data + " ");
/* now recur on right child */
printInorder(node.right);
}
// Driver Code
public static void Main(string[] args)
{
GFG tree = new GFG();
tree.root = new Node(50);
tree.root.left = new Node(7);
tree.root.right = new Node(2);
tree.root.left.left = new Node(3);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(1);
tree.root.right.right = new Node(30);
Console.WriteLine("Inorder traversal " +
"before conversion is :");
tree.printInorder(tree.root);
tree.convertTree(tree.root);
Console.WriteLine("");
Console.WriteLine("Inorder traversal " +
"after conversion is :");
tree.printInorder(tree.root);
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// JavaScript program to convert an arbitrary binary tree
// to a tree that holds children sum property
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
let root;
/* This function changes a tree to hold children sum
property */
function convertTree(node)
{
let left_data = 0, right_data = 0, diff;
/* If tree is empty or it's a leaf node then
return true */
if (node == null
|| (node.left == null && node.right == null))
return;
else
{
/* convert left and right subtrees */
convertTree(node.left);
convertTree(node.right);
/* If left child is not present then 0 is used
as data of left child */
if (node.left != null)
left_data = node.left.data;
/* If right child is not present then 0 is used
as data of right child */
if (node.right != null)
right_data = node.right.data;
/* get the diff of node's data and children sum */
diff = left_data + right_data - node.data;
/* If node's children sum is greater
than the node's data */
if (diff > 0)
node.data = node.data + diff;
/* THIS IS TRICKY --> If node's data
is greater than children
sum, then increment subtree by diff */
if (diff < 0)
// -diff is used to make diff positive
increment(node, -diff);
}
}
/* This function is used to increment subtree by diff */
function increment(node, diff)
{
/* IF left child is not NULL then increment it */
if (node.left != null)
{
node.left.data = node.left.data + diff;
// Recursively call to fix the
// descendants of node->left
increment(node.left, diff);
}
else if (node.right != null) // Else increment right child
{
node.right.data = node.right.data + diff;
// Recursively call to fix the
// descendants of node->right
increment(node.right, diff);
}
}
/* Given a binary tree, printInorder() prints out its
inorder traversal*/
function printInorder(node)
{
if (node == null)
return;
/* first recur on left child */
printInorder(node.left);
/* then print the data of node */
document.write(node.data + " ");
/* now recur on right child */
printInorder(node.right);
}
root = new Node(50);
root.left = new Node(7);
root.right = new Node(2);
root.left.left = new Node(3);
root.left.right = new Node(5);
root.right.left = new Node(1);
root.right.right = new Node(30);
document.write("Inorder traversal before conversion is :" +
"</br>");
printInorder(root);
convertTree(root);
document.write("</br>");
document.write("Inorder traversal after conversion is :" +
"</br>");
printInorder(root);
</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