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