Arboles

Tema 4: Árboles. Árboles binarios. T.A.D. 04/05
3
Altura de un nodo en un árbol es el número de nodos del camino más largo de ese nodo a una
hoja.
Altura del árbol es la altura de la raíz, o 0si el árbol es vacío.
Profundidad de un nodo es la longitud del camino único que va desde la raiz hasta ese nodo.
Se denomina grado de un nodo al número de hijos de dicho nodo.
El grado de unárbol es el mayor grado de los nodos que contiene.
El nivel de un nodo se asigna en función al criterio siguiente:
La raiz tiene nivel 1.
Si un nodo tiene nivel N, sus hijos tendrán nivel N+l.
El nºde niveles de un árbol es igual a la altura de su raíz, o a 0, si el árbol es vacío.
Conceptos menos utilizados son:
Longitud del camino externo: Suma de los niveles de cada nodo externo.Longitud del camino interno: Suma de los niveles de cada nodo interno.
Se utilizan distintas notaciones gráficas para
representar árboles. Entre ellas la más usual es el diagrama
de árbol invertido, queconsiste en utilizar un "árbol
invertido", representando la raíz en la parte superior, y,
debajo de ella, de izquierda a derecha, cada uno de sus
subárboles:
Los hijos de un nodo de orden Npueden estar
ordenados o desordenados. Los árboles resultantes son
ordenados y
desordenados respectivamente. Los siguientes
árboles ordenados no son equivalentes:
O sea, podemos ordenar o no a loshijos de un nodo,
lo cual dará lugar a diferentes conceptos de
igualdad.
En árboles de orden N se define:
Árbol lleno: es un árbol con todos sus niveles llenos. También podemos definirlo como elárbol
en el que la longitud del camino más largo y la del más corto desde cualquier nodo, son iguales.
Árbol Completo es un árbol con todos sus niveles llenos salvo quizás el último, que deberá estarcompleto, (sin "huecos") de izquierda a derecha.
Árbol perfectamente balanceado: Es aquél en el que el número de nodos de cada subárbol de
cada nodo interno, no varía en más de uno. La palabra...