Nurodyto skaičiaus faktorių medis
Faktorių medis yra intuityvus būdas suprasti skaičiaus veiksnius. Tai parodo, kaip visi veiksniai yra išvesti iš skaičiaus. Tai speciali diagrama, kurioje rasite skaičiaus veiksnius, tada tų skaičių veiksnius ir tt, kol nebegalite faktoriaus. Galai yra visi pirminiai pradinio skaičiaus veiksniai.
Pavyzdys:
Input : v = 48 Output : Root of below tree 48 / 2 24 / 2 12 / 2 6 / 2 3
Faktorių medis sukuriamas rekursyviai. Naudojamas dvejetainis medis.
- Pradedame nuo skaičiaus ir randame mažiausią galimą daliklį.
- Tada pirminį skaičių padalijame iš mažiausio daliklio.
- Tiek daliklį, tiek dalinį saugome kaip du pirminio skaičiaus antrinius.
- Abu vaikai siunčiami į funkciją rekursyviai.
- Jei daliklis, mažesnis nei pusė skaičiaus, nerandamas, du vaikai išsaugomi kaip NULL.
Įgyvendinimas:
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>
Išvestis
Level order traversal of constructed factor tree48 2 24 2 12 2 6 2 3
Laiko sudėtingumas: O(n) kur n yra nurodytas skaičius.
Erdvės sudėtingumas: O(k) čia k yra skaičiaus koeficientas.
Sukurti viktoriną
