Faktortre for et gitt tall
Faktortre er en intuitiv metode for å forstå faktorene til et tall. Den viser hvordan alle faktorene er utledet fra tallet. Det er et spesielt diagram hvor du finner faktorene til et tall og deretter faktorene til disse tallene osv. til du ikke kan faktorisere lenger. Endene er alle primfaktorene til det opprinnelige tallet.
Eksempel:
Input : v = 48 Output : Root of below tree 48 / 2 24 / 2 12 / 2 6 / 2 3
Faktortreet opprettes rekursivt. Det brukes et binært tre.
- Vi starter med et tall og finner den minste divisor som er mulig.
- Deretter deler vi foreldretallet med minstedeleren.
- Vi lagrer både divisor og kvotient som to barn av foreldrenummeret.
- Begge barna sendes i funksjon rekursivt.
- Hvis en divisor mindre enn halvparten av tallet ikke blir funnet, lagres to barn som NULL.
Implementering:
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>
Produksjon
Level order traversal of constructed factor tree48 2 24 2 12 2 6 2 3
Tidskompleksitet: O(n) hvor n er det gitte tallet.
Plass kompleksitet: O(k) hvor k er faktoren til tallet.
Lag quiz
