Árboles Binarios
Un árbol binario es una estructura de
datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho.
No pueden tener más de dos hijos (de ahí el nombre “binario”). Si algún hijo
tiene como referencia a null, es decir que no almacena ningún dato, entonces
este es llamado un nodo externo. En el caso contrario el hijo es llamado un
nodo interno. Usos comunes de los árboles binarios son los árboles binarios de
búsqueda, los montículos binarios y Codificación de Huffman.
Los Montículos
binarios
Un caso particular y sencillo de la estructura de
datos Montículo, y está basada en un árbol binario balanceado,
que puede verse como un árbol binario con dos restricciones adicionales:
·
Propiedad de montículo
Cada nodo contiene un valor superior al de sus hijos (para un montículo por
máximos) o más pequeño que el de sus hijos (para un montículo por mínimos).
· Árbol semi completo
El árbol está balanceado y en un mismo nivel las inserciones se realizan de
izquierda a derecha.
Los montículos por mínimos se utilizan frecuentemente para
representar colas de prioridad. A continuación se muestran dos montículos:
el primero por mínimos y el segundo por máximos, que representan el mismo
conjunto de valores y además son semi completos.
No hay comentarios.:
Publicar un comentario