Convierta un árbol binario arbitrario en un árbol que contenga la propiedad Children Sum

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *