Arbre factoriel d'un nombre donné
Factor Tree est une méthode intuitive pour comprendre les facteurs d'un nombre. Il montre comment tous les facteurs sont dérivés du nombre. C'est un diagramme spécial dans lequel vous trouvez les facteurs d'un nombre, puis les facteurs de ces nombres, etc. jusqu'à ce que vous ne puissiez plus factoriser. Les extrémités sont tous les facteurs premiers du nombre original.
Exemple:
Input : v = 48 Output : Root of below tree 48 / 2 24 / 2 12 / 2 6 / 2 3
L'arbre de facteurs est créé de manière récursive. Un arbre binaire est utilisé.
- Nous commençons par un nombre et trouvons le diviseur minimum possible.
- Ensuite, nous divisons le numéro parent par le diviseur minimum.
- Nous stockons à la fois le diviseur et le quotient comme deux enfants du nombre parent.
- Les deux enfants sont envoyés en fonction de manière récursive.
- Si un diviseur inférieur à la moitié du nombre n'est pas trouvé, deux enfants sont stockés comme NULL.
Mise en œuvre:
C++ // C++ program to construct Factor Tree for // a given number #include using namespace std ; // Tree node struct Node { struct Node * left * right ; int key ; }; // Utility function to create a new tree Node Node * newNode ( int key ) { Node * temp = new Node ; temp -> key = key ; temp -> left = temp -> right = NULL ; return temp ; } // Constructs factor tree for given value and stores // root of tree at given reference. void createFactorTree ( struct Node ** node_ref int v ) { ( * node_ref ) = newNode ( v ); // the number is factorized for ( int i = 2 ; i < v / 2 ; i ++ ) { if ( v % i != 0 ) continue ; // If we found a factor we construct left // and right subtrees and return. Since we // traverse factors starting from smaller // to greater left child will always have // smaller factor createFactorTree ( & (( * node_ref ) -> left ) i ); createFactorTree ( & (( * node_ref ) -> right ) v / i ); return ; } } // Iterative method to find the height of Binary Tree void printLevelOrder ( Node * root ) { // Base Case if ( root == NULL ) return ; queue < Node *> q ; q . push ( root ); while ( q . empty () == false ) { // Print front of queue and remove // it from queue Node * node = q . front (); cout < < node -> key < < ' ' ; q . pop (); if ( node -> left != NULL ) q . push ( node -> left ); if ( node -> right != NULL ) q . push ( node -> right ); } } // driver program int main () { int val = 48 ; // sample value struct Node * root = NULL ; createFactorTree ( & root val ); cout < < 'Level order traversal of ' 'constructed factor tree' ; printLevelOrder ( root ); return 0 ; }
Java // Java program to construct Factor Tree for // a given number import java.util.* ; class GFG { // Tree node static class Node { Node left right ; int key ; }; static Node root ; // Utility function to create a new tree Node static Node newNode ( int key ) { Node temp = new Node (); temp . key = key ; temp . left = temp . right = null ; return temp ; } // Constructs factor tree for given value and stores // root of tree at given reference. static Node createFactorTree ( Node node_ref int v ) { ( node_ref ) = newNode ( v ); // the number is factorized for ( int i = 2 ; i < v / 2 ; i ++ ) { if ( v % i != 0 ) continue ; // If we found a factor we construct left // and right subtrees and return. Since we // traverse factors starting from smaller // to greater left child will always have // smaller factor node_ref . left = createFactorTree ((( node_ref ). left ) i ); node_ref . right = createFactorTree ((( node_ref ). right ) v / i ); return node_ref ; } return node_ref ; } // Iterative method to find the height of Binary Tree static void printLevelOrder ( Node root ) { // Base Case if ( root == null ) return ; Queue < Node > q = new LinkedList <> (); q . add ( root ); while ( q . isEmpty () == false ) { // Print front of queue and remove // it from queue Node node = q . peek (); System . out . print ( node . key + ' ' ); q . remove (); if ( node . left != null ) q . add ( node . left ); if ( node . right != null ) q . add ( node . right ); } } // Driver program public static void main ( String [] args ) { int val = 48 ; // sample value root = null ; root = createFactorTree ( root val ); System . out . println ( 'Level order traversal of ' + 'constructed factor tree' ); printLevelOrder ( root ); } } // This code is contributed by Rajput-Ji
Python3 # Python program to construct Factor Tree for # a given number class Node : def __init__ ( self key ): self . left = None self . right = None self . key = key # Utility function to create a new tree Node def newNode ( key ): temp = Node ( key ) return temp # Constructs factor tree for given value and stores # root of tree at given reference. def createFactorTree ( node_ref v ): node_ref = newNode ( v ) # the number is factorized for i in range ( 2 int ( v / 2 )): if ( v % i != 0 ): continue # If we found a factor we construct left # and right subtrees and return. Since we # traverse factors starting from smaller # to greater left child will always have # smaller factor node_ref . left = createFactorTree ((( node_ref ) . left ) i ) node_ref . right = createFactorTree ((( node_ref ) . right ) int ( v / i )) return node_ref return node_ref # Iterative method to find the height of Binary Tree def printLevelOrder ( root ): # Base Case if ( root == None ): return q = []; q . append ( root ); while ( len ( q ) > 0 ): # Print front of queue and remove # it from queue node = q [ 0 ] print ( node . key end = ' ' ) q = q [ 1 :] if ( node . left != None ): q . append ( node . left ) if ( node . right != None ): q . append ( node . right ) val = 48 # sample value root = None root = createFactorTree ( root val ) print ( 'Level order traversal of constructed factor tree' ) printLevelOrder ( root ) # This code is contributed by shinjanpatra
C# // C# program to construct Factor Tree for // a given number using System ; using System.Collections.Generic ; public class GFG { // Tree node public class Node { public Node left right ; public int key ; }; static Node root ; // Utility function to create a new tree Node static Node newNode ( int key ) { Node temp = new Node (); temp . key = key ; temp . left = temp . right = null ; return temp ; } // Constructs factor tree for given value and stores // root of tree at given reference. static Node createFactorTree ( Node node_ref int v ) { ( node_ref ) = newNode ( v ); // the number is factorized for ( int i = 2 ; i < v / 2 ; i ++ ) { if ( v % i != 0 ) continue ; // If we found a factor we construct left // and right subtrees and return. Since we // traverse factors starting from smaller // to greater left child will always have // smaller factor node_ref . left = createFactorTree ((( node_ref ). left ) i ); node_ref . right = createFactorTree ((( node_ref ). right ) v / i ); return node_ref ; } return node_ref ; } // Iterative method to find the height of Binary Tree static void printLevelOrder ( Node root ) { // Base Case if ( root == null ) return ; Queue < Node > q = new Queue < Node > (); q . Enqueue ( root ); while ( q . Count != 0 ) { // Print front of queue and remove // it from queue Node node = q . Peek (); Console . Write ( node . key + ' ' ); q . Dequeue (); if ( node . left != null ) q . Enqueue ( node . left ); if ( node . right != null ) q . Enqueue ( node . right ); } } // Driver program public static void Main ( String [] args ) { int val = 48 ; // sample value root = null ; root = createFactorTree ( root val ); Console . WriteLine ( 'Level order traversal of ' + 'constructed factor tree' ); printLevelOrder ( root ); } } // This code is contributed by gauravrajput1
JavaScript < script > // Javascript program to construct Factor Tree for // a given number class Node { constructor ( key ) { this . left = null ; this . right = null ; this . key = key ; } } let root ; // Utility function to create a new tree Node function newNode ( key ) { let temp = new Node ( key ); return temp ; } // Constructs factor tree for given value and stores // root of tree at given reference. function createFactorTree ( node_ref v ) { ( node_ref ) = newNode ( v ); // the number is factorized for ( let i = 2 ; i < parseInt ( v / 2 10 ) ; i ++ ) { if ( v % i != 0 ) continue ; // If we found a factor we construct left // and right subtrees and return. Since we // traverse factors starting from smaller // to greater left child will always have // smaller factor node_ref . left = createFactorTree ((( node_ref ). left ) i ); node_ref . right = createFactorTree ((( node_ref ). right ) parseInt ( v / i 10 )); return node_ref ; } return node_ref ; } // Iterative method to find the height of Binary Tree function printLevelOrder ( root ) { // Base Case if ( root == null ) return ; let q = []; q . push ( root ); while ( q . length > 0 ) { // Print front of queue and remove // it from queue let node = q [ 0 ]; document . write ( node . key + ' ' ); q . shift (); if ( node . left != null ) q . push ( node . left ); if ( node . right != null ) q . push ( node . right ); } } let val = 48 ; // sample value root = null ; root = createFactorTree ( root val ); document . write ( 'Level order traversal of ' + 'constructed factor tree' + ' ' ); printLevelOrder ( root ); // This code is contributed by suresh07. < /script>
Sortir
Level order traversal of constructed factor tree48 2 24 2 12 2 6 2 3
Complexité temporelle : O(n) où n est le nombre donné.
Complexité spatiale : O(k) où k est le facteur du nombre.
Créer un quiz
