malformaciones

Arboles
Definición:
Un árbol dirigido es una estructura:
 Jerárquica porque los componentes están a distinto nivel.
 Organizada porque importa la forma en que esté dispuesto el contenido.
 Dinámica porque su forma, tamaño y contenido pueden variar durante la ejecución.
Un árbol puede ser:


a

vacío,

b

c

d

e

 Una raíz + subárboles.

f
 Mediante diagramas de Venn Mediante círculos y flechas

a

 Mediante paréntesis anidados:
( a ( b (e,f), c, d ) )

b
e

c

d

f

Conceptos Básicos
 Si hay un camino de A hasta B, se dice que A es antecesor de B, y que B es sucesor de A.
 Padre es el antecesor inmediato de un nodo
 Hijo, cualquiera de sus descendientes inmediatos.
 Descendiente de un nodo, es cualquier sucesor de dicho nodo.
Hermano de un nodo, es otro nodo con el mismo padre.
 Generación, es un conjunto de nodos con la misma profundidad.
 Los nodos de la misma generación tienen el mismo nivel.
 Grado de un nodo, es el número de flechas que salen de ese nodo (hijos). El número de las
que entran siempre es uno.
 Grado de un árbol, es el mayor grado que puede hallarse en sus nodos.

 Longitud del caminoentre 2 nodos: es el número de arcos que hay entre ellos.

Tipos de árboles
Un árbol ordenado: Es aquel en el que las ramas de los nodos están ordenadas.
 Los de grado 2 se llaman árboles binarios.
 Cada árbol binario tiene un subárbol izquierda y subárbol derecha.

 Árboles similares: Los que tienen la misma estructura (forma)

 Árboles Equivalentes: Son los árboles similares y sus nodoscontienen la misma
información.
 Árboles n-ario: Es un árbol ordenado cuyos nodos tiene N subárboles, y donde cualquier
número de subárboles puede ser árboles vacíos.

Árbol binario completo:
 Es un árbol en el que todos sus nodos, excepto los del último nivel, tienen dos hijos.

 Número de nodos en un árbol binario completo = 2h –1 (en el ejemplo h = 4,  15) esto
nos ayuda acalcular el nivel de árbol necesario para almacenar los datos de una
aplicación.

Árboles Binarios de Búsqueda
Un árbol es un ABB si éste es binario y sus nodos son subárboles de búsqueda binarios y
contienen información ordenada de tal que todos los elementos a la izquierda de la raíz
son menores a la raíz y todos los elementos a la derecha de la raíz son mayores a la raíz.

Características deun ABB
 Todos los nodos a la izquierda son menores al padre.
 Todos los nodos a la derecha son mayores al padre.
 Y solo pueden tener 2 hijos a lo mucho.

Conversión de un árbol general en un árbol binario
 Los hermanos se enlazan en forma horizontal (lineal)

 Se enlaza en forma vertical el padre con el hijo que se encuentra más a la izquierda y se
elimina el enlace de este padrecon los demás hijos.
 Se rota el diagrama resultante 45 grados hacia la izquierda.

Representación de un árbol binario en la memoria.
 Cada noto tiene la siguiente forma:

Clase nodo de un ABB
Class Nodo{
nodo izq;
nodo der;
int dato;
}

Operaciones sobre un árbol
 Recorrer árbol
 Preorden
 Inorden
 Postorden
 Inserción nodo
 Eliminar nodo
 Buscar nodo con información Sumar los nodos
 Calcular profundidad del árbol
 Contar nodos
 Contar hojas.

Recorridos de un árbol de Búsqueda Binaria (ABB)
Recorrido en preorden (prefijo)
 Visita la raíz.
 Recorre el subárbol izquierdo.
 Recorre el subárbol derecho.

PREORDEN (NODO)
{NODO es un dato de tipo apuntador}
{INFO, IZQ, DER son campos del registro}
Si nodo != null entonces
{
Visitar NODO{escribir NODO.INFO}
llamar a preorden con NODO.IZQ
{llamada recursiva a preorden con la
rama izquierda del nodo en cuestión}
llamar a preorden con NODO.DER
{llamada recursiva a preorden}

Recorrido en inorden (infijo)
 Recorre el subárbol izquierdo.
 Visita la raíz
 Recorre el subárbol derecho.

INORDEN (NODO)
{NODO es un apuntador a registro}
Si NODO != null entonces
{INORDEN...