Estructuras de datos | Árboles binarios | Pregunta 12

Un esquema para almacenar árboles binarios en una array X es el siguiente. La indexación de X comienza en 1 en lugar de 0. la raíz se almacena en X[1]. Para un Node almacenado en X[i], el hijo izquierdo, si lo hay, se almacena en X[2i] y el hijo derecho, si lo hay, en X[2i+1]. Para poder almacenar cualquier árbol binario en n vértices, el tamaño mínimo de X debe ser. (PUERTA CS 2006)

(A) log2n
(B) n
(C) 2n + 1
(D) 2^n — 1

Respuesta: (D)
Explicación: Para un árbol binario sesgado a la derecha, el número de Nodes será 2^n – 1. Por ejemplo, en el siguiente árbol binario, el Node ‘A’ se almacenará en el índice 1, ‘B’ en el índice 3, ‘C’ en el índice 7 y ‘D’ en el índice 15.

A
 \
   \
    B
      \
        \
         C
           \
             \
              D

Cuestionario de esta pregunta