Recuento de Nodes en un árbol binario con hijos inmediatos como sus factores

Dado un Árbol Binario , la tarea es imprimir el conteo de Nodes cuyos hijos inmediatos son sus factores

Ejemplos:  

Input: 
                  1
                /   \ 
              15     20
             /  \   /  \ 
            3    5 4     2 
                    \    / 
                     2  3  
Output: 2
Explanation: 
Children of 15 (3, 5)
 are factors of 15
Children of 20 (4, 2)
 are factors of 20

Input:
                  7
                /  \ 
              210   14 
             /  \      \
            70   14     30
           / \         / \
          2   5       10  15
                      /
                     23 
Output:3
Explanation: 
Children of 210 (70, 14)
 are factors of 210
Children of 70 (2, 5)
 are factors of 70
Children of 30 (10, 15)
 are factors of 30

Enfoque: para resolver este problema, debemos atravesar el árbol binario dado en orden de nivel y para cada Node con ambos hijos, verificar si ambos hijos tienen valores que son factores del valor del Node actual. Si es verdadero, cuente dichos Nodes e imprímalo al final.

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ program for Counting nodes
// whose immediate children
// are its factors
 
#include <bits/stdc++.h>
using namespace std;
 
// A Tree node
struct Node {
    int key;
    struct Node *left, *right;
};
 
// Utility function to create a new node
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return (temp);
}
 
// Function to check and print if
// immediate children of a node
// are its factors or not
bool areChilrenFactors(
    struct Node* parent,
    struct Node* a,
    struct Node* b)
{
    if (parent->key % a->key == 0
        && parent->key % b->key == 0)
        return true;
    else
        return false;
}
 
// Function to get the
// count of full Nodes in
// a binary tree
unsigned int getCount(struct Node* node)
{
    // If tree is empty
    if (!node)
        return 0;
    queue<Node*> q;
 
    // Do level order traversal
    // starting from root
    int count = 0;
    // Store the number of nodes
    // with both children as factors
    q.push(node);
    while (!q.empty()) {
        struct Node* temp = q.front();
        q.pop();
 
        if (temp->left && temp->right) {
            if (areChilrenFactors(
                    temp, temp->left,
                    temp->right))
                count++;
        }
 
        if (temp->left != NULL)
            q.push(temp->left);
        if (temp->right != NULL)
            q.push(temp->right);
    }
    return count;
}
 
// Function to find total no of nodes
// In a given binary tree
int findSize(struct Node* node)
{
    // Base condition
    if (node == NULL)
        return 0;
 
    return 1
           + findSize(node->left)
           + findSize(node->right);
}
 
// Driver Code
int main()
{
    /*        10
            / \
           40 36
              / \
             18  12
             / \ / \
            2  6 3 4
                  /
                 7
    */
 
    // Create Binary Tree as shown
    Node* root = newNode(10);
 
    root->left = newNode(40);
    root->right = newNode(36);
 
    root->right->left = newNode(18);
    root->right->right = newNode(12);
 
    root->right->left->left = newNode(2);
    root->right->left->right = newNode(6);
    root->right->right->left = newNode(3);
    root->right->right->right = newNode(4);
    root->right->right->right->left = newNode(7);
 
    // Print all nodes having
    // children as their factors
    cout << getCount(root) << endl;
 
    return 0;
}

Java

// Java program for Counting nodes
// whose immediate children
// are its factors
 import java.util.*;
 
class GFG{
  
// A Tree node
static class Node {
    int key;
    Node left, right;
};
  
// Utility function to create a new node
static Node newNode(int key)
{
    Node temp = new Node();
    temp.key = key;
    temp.left = temp.right = null;
    return (temp);
}
  
// Function to check and print if
// immediate children of a node
// are its factors or not
static boolean areChilrenFactors(
    Node parent,
    Node a,
    Node b)
{
    if (parent.key % a.key == 0
        && parent.key % b.key == 0)
        return true;
    else
        return false;
}
  
// Function to get the
// count of full Nodes in
// a binary tree
static int getCount(Node node)
{
    // If tree is empty
    if (node==null)
        return 0;
    Queue<Node> q = new LinkedList<Node>();
  
    // Do level order traversal
    // starting from root
    int count = 0;
 
    // Store the number of nodes
    // with both children as factors
    q.add(node);
    while (!q.isEmpty()) {
        Node temp = q.peek();
        q.remove();
  
        if (temp.left!=null && temp.right!=null) {
            if (areChilrenFactors(
                    temp, temp.left,
                    temp.right))
                count++;
        }
  
        if (temp.left != null)
            q.add(temp.left);
        if (temp.right != null)
            q.add(temp.right);
    }
    return count;
}
  
// Function to find total no of nodes
// In a given binary tree
static int findSize(Node node)
{
    // Base condition
    if (node == null)
        return 0;
  
    return 1
           + findSize(node.left)
           + findSize(node.right);
}
  
// Driver Code
public static void main(String[] args)
{
    /*        10
            / \
           40 36
              / \
             18  12
             / \ / \
            2  6 3 4
                  /
                 7
    */
  
    // Create Binary Tree as shown
    Node root = newNode(10);
  
    root.left = newNode(40);
    root.right = newNode(36);
  
    root.right.left = newNode(18);
    root.right.right = newNode(12);
  
    root.right.left.left = newNode(2);
    root.right.left.right = newNode(6);
    root.right.right.left = newNode(3);
    root.right.right.right = newNode(4);
    root.right.right.right.left = newNode(7);
  
    // Print all nodes having
    // children as their factors
    System.out.print(getCount(root) +"\n");
  
}
}
 
// This code is contributed by sapnasingh4991

Python3

# Python3 program for counting nodes
# whose immediate children
# are its factors
from collections import deque as queue
 
# A Binary Tree Node
class Node:
     
    def __init__(self, key):
         
        self.data = key
        self.left = None
        self.right = None
 
# Function to check and print if
# immediate children of a node
# are its factors or not
def areChildrenFactors(parent, a, b):
     
    if (parent.data % a.data == 0 and
        parent.data % b.data == 0):
        return True
    else:
        return False
 
# Function to get the
# count of full Nodes in
# a binary tree
def getCount(node):
     
    # Base Case
    if (not node):
        return 0
 
    q = queue()
 
    # Do level order traversal
    # starting from root
    count = 0
     
    # Store the number of nodes
    # with both children as factors
    q.append(node)
 
    while (len(q) > 0):
        temp = q.popleft()
        #q.pop()
 
        if (temp.left and temp.right):
            if (areChildrenFactors(temp, temp.left,
                                         temp.right)):
                count += 1
 
        if (temp.left != None):
            q.append(temp.left)
        if (temp.right != None):
            q.append(temp.right)
 
    return count
 
# Function to find total
# number of nodes
# In a given binary tree
def findSize(node):
     
    # Base condition
    if (node == None):
        return 0
 
    return (1 + findSize(node.left) + 
                findSize(node.right))
 
# Driver Code
if __name__ == '__main__':
     
    # /*        10
    #          / \
    #         40  36
    #            /  \
    #           18   12
    #           / \  / \
    #          2   6 3  4
    #                  /
    #                 7
    #  */
 
    # Create Binary Tree
    root = Node(10)
    root.left = Node(40)
    root.right = Node(36)
 
    root.right.left = Node(18)
    root.right.right = Node(12)
 
    root.right.left.left = Node(2)
    root.right.left.right = Node(6)
    root.right.right.left = Node(3)
    root.right.right.right = Node(4)
    root.right.right.right.left = Node(7)
 
    # Print all nodes having
    # children as their factors
    print(getCount(root))
 
# This code is contributed by mohit kumar 29

C#

// C# program for Counting nodes
// whose immediate children
// are its factors
using System;
using System.Collections.Generic;
 
class GFG{
   
// A Tree node
class Node {
    public int key;
    public Node left, right;
};
   
// Utility function to create a new node
static Node newNode(int key)
{
    Node temp = new Node();
    temp.key = key;
    temp.left = temp.right = null;
    return (temp);
}
   
// Function to check and print if
// immediate children of a node
// are its factors or not
static bool areChilrenFactors(
    Node parent,
    Node a,
    Node b)
{
    if (parent.key % a.key == 0
        && parent.key % b.key == 0)
        return true;
    else
        return false;
}
   
// Function to get the
// count of full Nodes in
// a binary tree
static int getCount(Node node)
{
    // If tree is empty
    if (node == null)
        return 0;
    List<Node> q = new List<Node>();
   
    // Do level order traversal
    // starting from root
    int count = 0;
  
    // Store the number of nodes
    // with both children as factors
    q.Add(node);
    while (q.Count != 0) {
        Node temp = q[0];
        q.RemoveAt(0);
   
        if (temp.left!=null && temp.right != null) {
            if (areChilrenFactors(
                    temp, temp.left,
                    temp.right))
                count++;
        }
   
        if (temp.left != null)
            q.Add(temp.left);
        if (temp.right != null)
            q.Add(temp.right);
    }
    return count;
}
   
// Function to find total no of nodes
// In a given binary tree
static int findSize(Node node)
{
    // Base condition
    if (node == null)
        return 0;
   
    return 1
           + findSize(node.left)
           + findSize(node.right);
}
   
// Driver Code
public static void Main(String[] args)
{
    /*        10
            / \
           40 36
              / \
             18  12
             / \ / \
            2  6 3 4
                  /
                 7
    */
   
    // Create Binary Tree as shown
    Node root = newNode(10);
   
    root.left = newNode(40);
    root.right = newNode(36);
   
    root.right.left = newNode(18);
    root.right.right = newNode(12);
   
    root.right.left.left = newNode(2);
    root.right.left.right = newNode(6);
    root.right.right.left = newNode(3);
    root.right.right.right = newNode(4);
    root.right.right.right.left = newNode(7);
   
    // Print all nodes having
    // children as their factors
    Console.Write(getCount(root) +"\n");
   
}
}
 
// This code is contributed by sapnasingh4991

Javascript

<script>
 
// Javascript program for Counting nodes
// whose immediate children are its factors
 
// A Tree node
class Node
{
     
    // Utility function to create a new node
    constructor(key)
    {
        this.key = key;
        this.left = this.right = null;
    }
}
 
// Function to check and print if
// immediate children of a node
// are its factors or not
function areChilrenFactors(parent, a, b)
{
    if (parent.key % a.key == 0 &&
        parent.key % b.key == 0)
        return true;
    else
        return false;
}
 
// Function to get the
// count of full Nodes in
// a binary tree
function getCount(node)
{
     
    // If tree is empty
    if (node == null)
        return 0;
         
    let q = [];
   
    // Do level order traversal
    // starting from root
    let count = 0;
  
    // Store the number of nodes
    // with both children as factors
    q.push(node);
     
    while (q.length != 0)
    {
        let temp = q.shift();
         
        if (temp.left != null &&
            temp.right != null)
        {
            if (areChilrenFactors(
                    temp, temp.left,
                    temp.right))
                count++;
        }
   
        if (temp.left != null)
            q.push(temp.left);
        if (temp.right != null)
            q.push(temp.right);
    }
    return count;
}
 
// Function to find total no of nodes
// In a given binary tree
function findSize(node)
{
     
    // Base condition
    if (node == null)
        return 0;
   
    return 1 + findSize(node.left) +
               findSize(node.right);
}
 
// Driver Code
 
/*          10
            / \
           40 36
              / \
             18  12
             / \ / \
            2  6 3 4
                  /
                 7
    */
   
// Create Binary Tree as shown
let root = new Node(10);
 
root.left = new Node(40);
root.right = new Node(36);
 
root.right.left = new Node(18);
root.right.right = new Node(12);
 
root.right.left.left = new Node(2);
root.right.left.right = new Node(6);
root.right.right.left = new Node(3);
root.right.right.right = new Node(4);
root.right.right.right.left = new Node(7);
 
// Print all nodes having
// children as their factors
document.write(getCount(root) + "<br>");
 
// This code is contributed by unknown2108
 
</script>
Producción: 

3

 

Publicación traducida automáticamente

Artículo escrito por Code_r y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *