Faktorový strom daného čísla
Faktorový strom je intuitívna metóda na pochopenie faktorov čísla. Ukazuje, ako sú z čísla odvodené všetky faktory. Je to špeciálny diagram, kde nájdete faktory čísla, potom faktory týchto čísel atď., kým už nemôžete faktorovať. Konce sú všetky prvočísla pôvodného čísla.
Príklad:
Input : v = 48 Output : Root of below tree 48 / 2 24 / 2 12 / 2 6 / 2 3
Faktorový strom sa vytvára rekurzívne. Používa sa binárny strom.
- Začneme číslom a nájdeme minimálneho možného deliteľa.
- Potom rodičovské číslo vydelíme minimálnym deliteľom.
- Deliteľ aj podiel uložíme ako dva potomky nadradeného čísla.
- Obe deti sú poslané do funkcie rekurzívne.
- Ak sa nenájde deliteľ menší ako polovica čísla, dva potomkovia sa uložia ako NULL.
Implementácia:
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>
Výstup
Level order traversal of constructed factor tree48 2 24 2 12 2 6 2 3
Časová zložitosť: O(n) kde n je dané číslo.
Priestorová zložitosť: O(k) kde k je činiteľ čísla.
Vytvoriť kvíz
![Top 10: Najhranejšie online hry na svete [v roku 2024]](https://techcodeview.com/img/health-lifestyle/63/top-10-most-played-online-games-world.webp)
