Recuento de Nodes que están a una distancia X de la raíz y las hojas

Dados dos enteros N y X , donde N es el número de Nodes en un árbol binario casi completo . La tarea es encontrar: 

  1. El número de Nodes que están a una distancia X de la raíz.
  2. El número de Nodes que están a una distancia X de cualquier hoja en su subárbol.

Nota: Un árbol binario completo es un árbol binario en el que todos los niveles, excepto posiblemente el último, están completamente llenos y todos los Nodes están lo más a la izquierda posible.

Ejemplos: 

Input: N = 6, X = 0
Output: 
1
3
Complete Binary Tree of 6 nodes is
         1
       /    \  
      2      3 
    /  \    / 
   4    5  6
Nodes that are at 0 distance from root = 1 (root itself).
Nodes that are at 0 distance from any of the leaf = 3 (all the leaves of the tree)

Input: N = 13, X = 1
Output:
2
4
Complete Binary Tree of 13 nodes.
                       1
                  /         \  
                2             3 
              /   \         /   \
            4      5       6     7
          /  \    /  \   /  \  
         8    9  10  11 12  13
Nodes that are at 0 distance from root = 2 (node no. 2 and 3)
Nodes that are at 0 distance from any of the leaf = 4 (node no. 4, 5, 6 and 3)

Acercarse:  

  1. Encontrar el número de Nodes que están a una distancia x de la raíz es simple. Simplemente imprimimos el número de Nodes a la x-ésima altura. Sabemos que en un árbol binario completo todos los niveles están completos, excepto posiblemente el último y todos los Nodes están lo más a la izquierda posible. Entonces, la altura h de un árbol binario completo se calcula como piso (log2 (n)) donde n es el número total de Nodes. Además, el número de Nodes en la i-ésima altura será 2 i y el número de Nodes que están en el último nivel (es decir, en la altura h) = 2 h – (max_total_nodes – n) , donde 2 h son Nodes máximos en la altura h .
  2. Encontrar el número de Nodes que están a una distancia x de cualquier hoja en su subárbol es un poco complicado. Se trata de observar el hecho de que si tenemos l Nodes hoja entonces, los Nodes ceil(l/2) están a 1 unidad de distancia de las hojas, los Nodes ceil(l/4) están a 2 unidades de distancia de las hojas…. hasta ceil(l/2 i ) los Nodes están a i unidades de distancia de las hojas. Primero encontraremos el conteo de Nodes hoja y aplicaremos el método anterior para encontrar Nodes que estén a una distancia x de la hoja.

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

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the count
// of the required nodes
void countNodes(int N, int X)
{
 
    // Height of the complete binary
    // tree with n nodes
    int height = floor(log2(N));
 
    // If X > height then no node
    // can be present at that level
    if (X > height) {
        cout << "0\n0";
        return;
    }
 
    // Corner case
    if (N == 1) {
        cout << "1\n1";
        return;
    }
 
    // Maximum total nodes that are possible
    // in complete binary tree with height h
    int max_total_nodes = (1 << (height + 1)) - 1;
 
    // Nodes at the last level
    int nodes_last_level
        = (1 << height) - (max_total_nodes - N);
 
    // To store the count of nodes
    // x dist away from root
    int from_root;
 
    // To store the count of nodes
    // x dist away from leaf
    int from_leaf;
 
    // If X = h then print nodes at last level
    // else nodes at Xth level
    if (X == height)
        from_root = nodes_last_level;
 
    // 2^X
    else
        from_root = 1 << X;
 
    // Number of left leaf nodes at (h-1)th level
    // observe that if nodes are not present at last level
    // then there are a/2 leaf nodes at (h-1)th level
    int left_leaf_nodes
        = ((1 << height) - nodes_last_level) / 2;
 
    // If X = h then print leaf nodes at the last h level
    // + leaf nodes at (h-1)th level
    if (X == 0) {
        from_leaf = nodes_last_level + left_leaf_nodes;
    }
    else {
 
        // First calculate nodes for leaves present at
        // height h
        int i = X;
 
        while (nodes_last_level > 1 && i > 0) {
            nodes_last_level
                = ceil((float)nodes_last_level / (float)2);
            i--;
        }
 
        from_leaf = nodes_last_level;
 
        // Then calculate nodes for leaves present at height
        // h-1
        i = X;
        while (left_leaf_nodes > 1 && i > 0) {
            left_leaf_nodes
                = ceil((float)left_leaf_nodes / (float)2);
            i--;
        }
 
        // Add both the results
        from_leaf += left_leaf_nodes;
    }
 
    cout << from_root << endl << from_leaf;
}
 
// Driver code
int main()
{
    int N = 38, X = 3;
 
    countNodes(N, X);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG {
 
    // Function to find the count
    // of the required nodes
    static void countNodes(int N, int X)
    {
 
        // Height of the complete binary
        // tree with n nodes
        int height
            = (int)Math.floor(Math.log(N) / Math.log(2));
 
        // If X > height then no node
        // can be present at that level
        if (X > height) {
            System.out.println("0\n0");
            return;
        }
 
        // Corner case
        if (N == 1) {
            System.out.println("1\n1");
            return;
        }
 
        // Maximum total nodes that are possible
        // in complete binary tree with height h
        int max_total_nodes = (1 << (height + 1)) - 1;
 
        // Nodes at the last level
        int nodes_last_level
            = (1 << height) - (max_total_nodes - N);
 
        // To store the count of nodes
        // x dist away from root
        int from_root;
 
        // To store the count of nodes
        // x dist away from leaf
        int from_leaf;
 
        // If X = h then print nodes at last level
        // else nodes at Xth level
        if (X == height)
            from_root = nodes_last_level;
 
        // 2^X
        else
            from_root = 1 << X;
 
        // Number of left leaf nodes at (h-1)th level
        // observe that if nodes are not present at last
        // level then there are a/2 leaf nodes at (h-1)th
        // level
        int left_leaf_nodes
            = ((1 << height) - nodes_last_level) / 2;
 
        // If X = h then print leaf nodes at the last h
        // level
        // + leaf nodes at (h-1)th level
        if (X == 0) {
            from_leaf = nodes_last_level + left_leaf_nodes;
        }
        else {
 
            // First calculate nodes for leaves present at
            // height h
            int i = X;
 
            while (nodes_last_level > 1 && i > 0) {
                nodes_last_level = (int)Math.ceil(
                    (float)nodes_last_level / (float)2);
                i--;
            }
 
            from_leaf = nodes_last_level;
 
            // Then calculate nodes for leaves present at
            // height h-1
            i = X;
            while (left_leaf_nodes > 1 && i > 0) {
                left_leaf_nodes = (int)Math.ceil(
                    (float)left_leaf_nodes / (float)2);
                i--;
            }
 
            // Add both the results
            from_leaf += left_leaf_nodes;
        }
 
        System.out.println(from_root + "\n" + from_leaf);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 38, X = 3;
        countNodes(N, X);
    }
}
 
// This code is contributed by
// sanjeev2552

Python3

# Python3 implementation of the approach
from math import log2, ceil, floor
 
# Function to find the count
# of the required nodes
def countNodes(N, X):
 
    # Height of the complete binary
    # tree with n nodes
    height = floor(log2(N))
 
    # If X > height then no node
    # can be present at that level
    if (X > height):
        print("0\n0")
        return
 
    # Corner case
    if (N == 1):
        print("1\n1")
        return
 
    # Maximum total nodes that are possible
    # in complete binary tree with height h
    max_total_nodes = (1 << (height + 1)) - 1
 
    # Nodes at the last level
    nodes_last_level = (1 << height) - (max_total_nodes - N)
 
    # To store the count of nodes
    # x dist away from root
    from_root = 0
 
    # To store the count of nodes
    # x dist away from leaf
    from_leaf = 0
 
    # If X = h then print nodes at last level
    # else nodes at Xth level
    if (X == height):
        from_root = nodes_last_level
 
    # 2^X
    else:
        from_root = 1 << X
 
    # Number of left leaf nodes at (h-1)th level
    # observe that if nodes are not present at last level
    # then there are a/2 leaf nodes at (h-1)th level
    left_leaf_nodes = ((1 << height) - nodes_last_level) // 2
 
    # If X = h then print leaf nodes at the last h level
    # + leaf nodes at (h-1)th level
    if (X == 0):
        from_leaf = nodes_last_level + left_leaf_nodes
    else:
        # First calculate nodes for leaves present at
        # height h
        i = X
 
        while (nodes_last_level > 1 and i > 0):
            nodes_last_level = ceil(nodes_last_level / 2)
            i-=1
 
        from_leaf = nodes_last_level
 
        # Then calculate nodes for leaves present at height
        # h-1
        i = X
        while (left_leaf_nodes > 1 and i > 0):
            left_leaf_nodes = ceil(left_leaf_nodes / 2)
            i -= 1
 
        # Add both the results
        from_leaf += left_leaf_nodes
 
    print(from_root)
    print(from_leaf)
 
# Driver code
if __name__ == '__main__':
    N, X = 38, 3
 
    countNodes(N, X)
 
    # This code is contributed by mohit kumar 29.

C#

// C# implementation of the approach
using System;
 
class GFG{
 
// Function to find the count
// of the required nodes
static void countNodes(int N, int X)
{
     
    // Height of the complete binary
    // tree with n nodes
    int height = (int)Math.Floor(Math.Log(N) /
                                 Math.Log(2));
 
    // If X > height then no node
    // can be present at that level
    if (X > height)
    {
        Console.Write("0\n0");
        return;
    }
 
    // Corner case
    if (N == 1)
    {
        Console.Write("1\n1");
        return;
    }
 
    // Maximum total nodes that are possible
    // in complete binary tree with height h
    int max_total_nodes = (1 << (height + 1)) - 1;
 
    // Nodes at the last level
    int nodes_last_level = (1 << height) -
                           (max_total_nodes - N);
 
    // To store the count of nodes
    // x dist away from root
    int from_root;
 
    // To store the count of nodes
    // x dist away from leaf
    int from_leaf;
 
    // If X = h then print nodes at last level
    // else nodes at Xth level
    if (X == height)
        from_root = nodes_last_level;
 
    // 2^X
    else
        from_root = 1 << X;
 
    // Number of left leaf nodes at (h-1)th level
    // observe that if nodes are not present at last
    // level then there are a/2 leaf nodes at (h-1)th
    // level
    int left_leaf_nodes = ((1 << height) -
                           nodes_last_level) / 2;
 
    // If X = h then print leaf nodes at the last h
    // level
    // + leaf nodes at (h-1)th level
    if (X == 0)
    {
        from_leaf = nodes_last_level +
                    left_leaf_nodes;
    }
    else
    {
         
        // First calculate nodes for leaves present
        // at height h
        int i = X;
 
        while (nodes_last_level > 1 && i > 0)
        {
            nodes_last_level = (int)Math.Ceiling(
                (float)nodes_last_level / (float)2);
                 
            i--;
        }
 
        from_leaf = nodes_last_level;
 
        // Then calculate nodes for leaves present at
        // height h-1
        i = X;
        while (left_leaf_nodes > 1 && i > 0)
        {
            left_leaf_nodes = (int)Math.Ceiling(
                (float)left_leaf_nodes / (float)2);
                 
            i--;
        }
 
        // Add both the results
        from_leaf += left_leaf_nodes;
    }
 
    Console.Write(from_root + "\n" + from_leaf);
}
 
// Driver Code
public static void Main()
{
    int N = 38, X = 3;
    countNodes(N, X);
}
}
 
// This code is contributed by subham348

Javascript

<script>
 
// Javascript implementation of the approach
 
// Function to find the count
// of the required nodes
function countNodes(N, X)
{
     
    // Height of the complete binary
    // tree with n nodes
    let height = Math.floor(Math.log(N) /
                            Math.log(2));
 
    // If X > height then no node
    // can be present at that level
    if (X > height)
    {
        document.write("0<br>0");
        return;
    }
 
    // Corner case
    if (N == 1)
    {
        document.write("1<br>1");
        return;
    }
 
    // Maximum total nodes that are possible
    // in complete binary tree with height h
    let max_total_nodes = (1 << (height + 1)) - 1;
 
    // Nodes at the last level
    let nodes_last_level = (1 << height) -
                           (max_total_nodes - N);
 
    // To store the count of nodes
    // x dist away from root
    let from_root;
 
    // To store the count of nodes
    // x dist away from leaf
    let from_leaf;
 
    // If X = h then print nodes at last level
    // else nodes at Xth level
    if (X == height)
        from_root = nodes_last_level;
 
    // 2^X
    else
        from_root = 1 << X;
 
    // Number of left leaf nodes at (h-1)th level
    // observe that if nodes are not present at last
    // level then there are a/2 leaf nodes at (h-1)th
    // level
    let left_leaf_nodes = Math.floor(
        ((1 << height) - nodes_last_level) / 2);
 
    // If X = h then print leaf nodes at the last h
    // level
    // + leaf nodes at (h-1)th level
    if (X == 0)
    {
        from_leaf = nodes_last_level +
                    left_leaf_nodes;
    }
    else
    {
         
        // First calculate nodes for leaves
        // present at height h
        let i = X;
 
        while (nodes_last_level > 1 && i > 0)
        {
            nodes_last_level = Math.floor(Math.ceil(
                nodes_last_level / 2));
            i--;
        }
 
        from_leaf = nodes_last_level;
 
        // Then calculate nodes for leaves present at
        // height h-1
        i = X;
        while (left_leaf_nodes > 1 && i > 0)
        {
            left_leaf_nodes = Math.floor(Math.ceil(
                left_leaf_nodes / 2));
            i--;
        }
 
        // Add both the results
        from_leaf += left_leaf_nodes;
    }
    document.write(from_root + "<br>" + from_leaf);
}
 
// Driver Code
let N = 38, X = 3;
countNodes(N, X);
 
// This code is contributed by unknown2108
 
</script>
Producción: 

8
3

 

Complejidad del tiempo: O(log (N) )

Espacio Auxiliar: O(1), ya que no se ha ocupado ningún espacio extra.

Publicación traducida automáticamente

Artículo escrito por tyagikartik4282 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 *