Factor Tree es un método intuitivo para comprender los factores de un número. Muestra cómo todos los factores se derivan del número. Es un diagrama especial donde encuentras los factores de un número, luego los factores de esos números, etc. hasta que ya no puedes factorizar. Los extremos son todos los factores primos del número original.
Ejemplo:
Input : v = 48
Output : Root of below tree
48
/\
2 24
/\
2 12
/\
2 6
/\
2 3
El árbol de factores se crea recursivamente. Se utiliza un árbol binario.
- Empezamos con un número y encontramos el mínimo divisor posible.
- Luego, dividimos el número padre por el divisor mínimo.
- Almacenamos tanto el divisor como el cociente como dos hijos del número padre.
- Ambos niños son enviados a funcionar recursivamente.
- Si no se encuentra un divisor menor que la mitad del número, dos hijos se almacenan como NULL.
Implementación:
C++
// C++ program to construct Factor Tree for
// a given number
#include<bits/stdc++.h>
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" + "</br>");
printLevelOrder(root);
// This code is contributed by suresh07.
</script>
Producción
Level order traversal of constructed factor tree48 2 24 2 12 2 6 2 3
Este artículo es una contribución de Suprotik Dey . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA