Estructuras de Datos ARBOLES Binario AVL B




ESCUELA POLITECNICA NACIONAL



FACULTAD DE INGENIERÍA DE SISTEMAS

Estructura de Datos
GRUPO # 04

ÁRBOLES






ARBOL BINARIO

1. OBJETIVOS:
Aprender sobre la estructura y propiedades de un árbol binario.
2. MARCO TEORICO:
Árboles binarios
Son estructuras de datos de tipo no lineal y dinámicas
Existen varias clases de árboles binarios, como los balanceados (AVL), B, B+, etc.; los AVLse usan en la memoria principal, y los B+ se usan en memorias externas
La definición formal de un árbol binario según Cairo, es una estructura de datos jerárquica aplicada sobre una colección de elementos.
Existen varias aplicaciones de los árboles binarios, como:
Para fórmulas matemáticas
Árboles genealógicos
Enumeración de capítulos y secciones en los libros.
Se dice que todo árbol que no esvacío tiene un único nodo raíz. Un nodo X es descendiente directo de un nodo Y si X es apuntado por Y (“X es hijo de Y”). Un nodo X es antecesor directo de un nodo Y si el nodo X apunta al nodo Y (“X es padre de Y”).
Conceptos:
Nodos hermanos: Aquellos nodos que son descendientes directos del mismo nodo.
Nodo terminal: Llamado también hoja, aquel nodo que no tiene ramificaciones.
Nodo interior: Todonodo que no es hoja ni raíz.
Grado: Número de descendientes directos de un nodo.
Grado del árbol: Máximo grado de los nodos del árbol.
Nivel: Número de arcos que deben ser recorridos para llegar a un determinado nodo. La raíz tiene nivel 1.
Camino: Recorrido desde un nodo origen hasta un nodo destino.
Longitud de camino: Número de arcos que deben ser recorridos desde el nodo raíz hasta un nodoX.
Longitud de Camino Interno (LCI): Suma de todas las longitudes de camino de todos los nodos del árbol. Permite conocer los caminos que tiene el árbol.


Medida de Longitud de Camino Interno (LCIM): Nos ayuda a ver el mejor camino partiendo del nodo raíz

Árbol extendido: Árbol cuyo número de hijos de cada nodo es igual al grado del árbol. Si algún nodo no cumple la condición, deben incorporarsetantos nodos especiales como se requieran. Los nodos especiales se representan con cuadrados.
Longitud de Camino Externo: Nos ayuda a tomar la mejor decisión, qué camino tomar.

Para pasar de un árbol general a un árbol binario se deben seguir los siguientes pasos:
1.- Enlazar los hijos de cada nodo en forma horizontal.
2.- Relacionar de forma vertical el nodo padre con el hijo que se encuentramás a la izquierda.
3.- Rotar el diagrama resultante aproximadamente 45° a la izquierda y así obtenemos el árbol binario resultante.

3. DESARROLLO:
1.- Transformar el árbol general a árbol binario.




2.- Hacer el recorrido In-orden del siguiente árbol binario.

Respuesta: C-B-E-F-D-A.
4. EJERCICIOS:
package consulta;

public class Arbolbinario {
class Nodo
{
int info;Nodo izq, der;
}
Nodo raiz;

public Arbolbinario() {
raiz=null;
}

public void insertar (int info)
{
Nodo nuevo;
nuevo = new Nodo ();
nuevo.info = info;
nuevo.izq = null;
nuevo.der = null;
if (raiz == null)
raiz = nuevo;
else
{
Nodoanterior = null, reco;
reco = raiz;
while (reco != null)
{
anterior = reco;
if (info < reco.info)
reco = reco.izq;
else
reco = reco.der;
}
if (info < anterior.info)
anterior.izq = nuevo;
elseanterior.der = nuevo;
}
}


private void imprimirPre (Nodo reco)
{
if (reco != null)
{
System.out.print(reco.info + " ");
imprimirPre (reco.izq);
imprimirPre (reco.der);
}
}

public void imprimirPre ()
{
imprimirPre (raiz);
System.out.println();
}...