Los árboles son importantes para conceptualizar algunos algoritmos. Esto se debe a que muchos problemas pueden ser resueltos imaginando como son las posibles respuestas.
Arboles y Arboles binarios son básicamente listas enlazadas a través de apuntadores. En el caso de árboles binarios, estos tienen en cada nodo, potencialmente dos hijos: un hijo izquierdo y un hijo derecho. El nodo hasta el tope del árbol es el nodo raiz.
Cuando un árbol tiene únicamente un nodo, su altura es de uno. Los que tienen un par de hijos tienen altura de dos y, así sucesivamente.
La altura o profundidad de un árbol indica tambien el número de niveles que tiene. Un árbol que tiene solo el nodo raiz, tiene un nivel, los que tienen un para de hijos tendrán dos niveles y, así sucesivamente.
En un árbol binario, el número de nodos en cada nivel, se incrementa con una potencia de dos:
Nivel nodos del nivel total nodos
1 1 1
2 2 3
3 4 8
..
k 2k-1 2k-1
El número máximo de nodos sobre el nivel k es 2exp(k-1). El número máximo de nodos en un árbol binario de profundidad k es 2k-1.
Un árbol binario de profundidad k que tiene exactamente 2k-1 nodos, se llama un árbol binario completo.
Una forma de representar un árbol binario es en forma secuencial, empezando con el nodo raiz y siguiendo de izaquierda a derecha en cada nivel. Un árbol binario con n nodos y de profundidad k es completo si sus nodos corresponden a los nodos que numeran a n en el árbol binario de profundidad k.Como consecuencia, en un árbol completo, pueden ser almacenados en forma compacta en un arreglo ARBOL unidimensional. Es entonces fácil de determinar la localización de cualquier nodo padre o hijo izquierdo o derecho.
Referencias. Faltan.
ResponderEliminar+2