Considere un montón binario de tamaño N. Necesitamos encontrar su altura.
Ejemplos:
Input : N = 6 Output : 2 () / \ () () / \ / () () () Input : N = 9 Output : 3 () / \ () () / \ / \ () () () () / \ () ()
Sea N el tamaño del montón y h la altura . Si tomamos algunos ejemplos, podemos notar que el valor de h en un árbol binario completo es piso (log 2 N).
Ejemplos:
N h --------- 1 0 2 1 3 1 4 2 5 2 ..... .....
Implementación:
C++
// CPP program to find height of complete // binary tree from total nodes. #include <bits/stdc++.h> using namespace std; int height(int N) { return floor(log2(N)); } // driver node int main() { int N = 2; cout << height(N); return 0; }
Java
// Java program to find height // of complete binary tree // from total nodes. import java.lang.*; class GFG { // Function to calculate height static int height(int N) { return (int)Math.ceil(Math.log(N + 1) / Math.log(2)) - 1; } // Driver Code public static void main(String[] args) { int N = 6; System.out.println(height(N)); } } // This code is contributed by // Smitha Dinesh Semwal
Python 3
# Python 3 program to find # height of complete binary # tree from total nodes. import math def height(N): return math.ceil(math.log2(N + 1)) - 1 # driver node N = 6 print(height(N)) # This code is contributed by # Smitha Dinesh Semwal
C#
// C# program to find height // of complete binary tree // from total nodes. using System; class GFG { static int height(int N) { return (int)Math.Ceiling(Math.Log(N + 1) / Math.Log(2)) - 1; } // Driver node public static void Main() { int N = 6; Console.Write(height(N)); } } // This code is contributed by // Smitha Dinesh Semwal
PHP
<?php // PHP program to find height // of complete binary tree // from total nodes. function height($N) { return ceil(log($N + 1, 2)) - 1; } // Driver Code $N = 6; echo height($N); // This code is contributed by aj_36 ?>
Javascript
<script> // Javascript program to find height // of complete binary tree // from total nodes. function height(N) { return Math.ceil(Math.log(N + 1) / Math.log(2)) - 1; } let N = 6; document.write(height(N)); </script>
Producción
1
Complejidad Temporal : O(1), Desde la realización de operaciones constantes.
Espacio Auxiliar: O(1), Ya que se usa espacio extra constante.
Publicación traducida automáticamente
Artículo escrito por Shashank_Pathak y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA