Faktorbaum einer gegebenen Zahl
Faktorbaum ist eine intuitive Methode, um die Faktoren einer Zahl zu verstehen. Es zeigt, wie alle Faktoren aus der Zahl abgeleitet werden. Es handelt sich um ein spezielles Diagramm, in dem Sie die Faktoren einer Zahl, dann die Faktoren dieser Zahlen usw. finden, bis Sie nicht mehr faktorisieren können. Die Enden sind alle Primfaktoren der ursprünglichen Zahl.
Beispiel:
Input : v = 48 Output : Root of below tree 48 / 2 24 / 2 12 / 2 6 / 2 3
Der Faktorbaum wird rekursiv erstellt. Es wird ein Binärbaum verwendet.
- Wir beginnen mit einer Zahl und finden den kleinstmöglichen Teiler.
- Dann dividieren wir die übergeordnete Zahl durch den Mindestteiler.
- Wir speichern sowohl den Divisor als auch den Quotienten als zwei untergeordnete Elemente der übergeordneten Zahl.
- Beide Kinder werden rekursiv in die Funktion geschickt.
- Wenn kein Teiler gefunden wird, der kleiner als die Hälfte der Zahl ist, werden zwei untergeordnete Elemente als NULL gespeichert.
Durchführung:
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>
Ausgabe
Level order traversal of constructed factor tree48 2 24 2 12 2 6 2 3
Zeitkomplexität: O(n) wobei n die angegebene Zahl ist.
Raumkomplexität: O(k) wobei k der Faktor der Zahl ist.
Quiz erstellen
