1° Definiciones Básicas

2° Estructuras:

- Lineales (listas, colas, bicolas, pilas...)

- No Lineales (árboles)

3° Estructuras Recursivas

4° Estructuras Relacionales

5° Ordenamiento y Búsqueda

6° Mapa Conceptual

7° Estructuras Recursivas:

-Arboles

8° Algoritmo Basico

- Clase Nodo Binario

- Clase Árbol Binario

- Tamaño

- Altura

9° Recorridos

- Pre-Orden

- In-Orden

- Post-Orden

9° Arbol B

10° Arbol B+

11 ° Mapa Conceptual Arboles

12° Programa Recorrido Arbol

13° Exposición Ordenamiento por HeapSort

Exposición Ordenamiento por HeapSort

Programa Recorrido Arbol

public class Test
{
public static void main(String args[])
  {
  CArbolBinarioDeBusqueda arbolbb=new CArbolBinarioDeBusqueda();
  String nombre;
  double nota;
  int i=0,cod;
  System.out.println("Introducir datos. Finalizar con Ctrl+z.");
  System.out.println("nombre: ");
  while((nombre=Leer.dato())!=null)
 {
  System.out.print("nota: ");
  nota=Leer.datoDouble();
  cod=arbolbb.insertar(new CDatos(nombre,nota));
  if(cod==CArbolBinarioDeBusqueda.YA_EXISTE)
  {
  CDatos datos=(CDatos)arbolbb.buscar(new CDatos(nombre,nota));
   if(nota>=0)
   datos.asignarNota(nota);
    else
   {
   if(arbolbb.borrar(new CDatos(nombre,nota))==null)
  System.out.println("nodo borrado porque no existe");
  else
  System.out.println("nodo borrado");
 }
  }
  System.out.print("nombre: ");
  }
   System.out.println("\n");
               
  System.out.println("\nArbolInorden: ");
 arbolbb.visitarInorden();
 System.out.println("\nArbol posorden: ");

 arbolbb.visitarPosorden();

 System.out.println("\nArbol preorden: ");

 arbolbb.visitarPreorden();
                }
}

SeudoCodigo Recorrido Arbol

 

Mapa Conceptual Arboles

Para ver imagen completa presione clic Aquí ...............

Arbol B+

Arbol B+

     Caracteristicas:

• Nodos internos solo contienen las claves o apuntadores
• Todas las hojas se encuentran al mismo nivel
• Nodos hojas se encuentran ligadas como una lista enlazada para permitir la busqueda mas eficiente 
• El minimo numero de Claves es 2

EJEMPLO:

Construir TB+[37,48,55,61,73,77,80,87,92]

Arbol B

Arbol B

   Caracteristicas:

•  Conserva las caracteristivas del arbol binario, AVL, ABB
  
• Se busca la clave a insertar
• Si no esta en el arbol se comienza a insertar
• ¿ Esta llena la Pagina?
• Se divide la pagina en 2 paginas el mismo nivel , extrayendo la clave media 
• Con esta medida se sube por el camino de busqueda y se comienza el proceso nuevamente

EJEMPLO: 

Construir el arbol B  TB=[55,77,37,48,61,73,80,87,87,92]

Recorridos

Preorden

void preorder (){
System.out.println(d);
if (izq != null)
izq.preorder();
if (der != null)
der.preorder();
}

Postorden

void postorder (){
if (izq != null)
izq.postorder();
if (der != null)
der postorder();
der.System.out.println(d);
}

Inorden

void inorder (){
if (izq != null)
izq.inorder();
System.out.println(d);
if (der != null)
der.inorder();
}

Algoritmo Basico

Algoritmo Basico

• Tamaño (número de nodos)
• Profundidad de un nodo
• Altura
• Recorridos
• Euler
• Pre-, in- y post-orden
• Suponemos árboles binarios para simplifica

Clase Nodo binario

Class NodoB {
Object d;
NodoB izq;
NodoB der;
NodoB() {this(null);}
NodoB(Object o) {this(o,null,null);}
NodoB(Object o, NodoB i, NodoB d)
{d=o; izq=i; der=d;}
static int size ( NodoB a){...;}
static int height (NodoB a){...;}
void preorder (NodoB a){...;}
void inorder (NodoB a){...;}
void postorder (NodoB a){...;}
}

Clase Árbol binario

protected NodoB raiz;
ArbolB() {raiz=null;}
ArbolB(Object o){raiz=new NodoB(o);}
public int size()
{return NodoB.size(raiz);}
public int height()
{return NodoB.height(raiz);}
public void preorder ()
p p {if (raiz!=null) raiz.preorder();}
public void inorder ()
{if (raiz!=null) raiz.inorder();}
public void postorder ()
{if (raiz!=null) raiz.postorder();}
}

 Tamaño

static int size (NodoB a){
if (a==null)
return 0;
else
return 1+size(a.izq)+size(a.der);
}

Altura

 
static int height (NodoB a){
if (a==null)
return (-1);
else
return 1+Math.max(height(a.izq),
height(a.der));
}

Estructuras Recursivas

ÁRBOLES

Árboles: Es un conjunto de nodos, en cada nodo hay información.

Características:

• Árbol vacio T = 0
• Raíz: se desprenden los subárboles.
• Longitud: cantidad de ramas o aristas desde la raíz hasta el nodo de referencia.
• Profundidad: niveles de árbol, desde la raíz hasta nodo más profundo.
• Grado: la cantidad de ramas en una sola raíz.
• Recorrido: ancho, preorden, inorden y postorden.
• Tamaño: el número de nodos que tiene el árbol.
• Árbol binario: es cuando el grado del árbol es 2.
• Árbol de busqueda: contiene un factor de equilibrio dado por la altura del hijo derecho menos (-) el hijo izquierdo. FE <= 1

Operaciones árboles

• Buscar
• Insertar
• Eliminar

"recorrido inorden es el que ordena un árbol"

"árbol de busqueda organizado AVAL"

"árbol degenerado: que queda todo hacia un solo lado"

IMPLEMENTACIÓN DE ÁRBOLES BINARIOS

• arreglo: estructura estática.
• como estructuras ligadas se debe definir el tamaño del arreglo y NUNCA cambiarlo.
• overflow: desborde de información.

Árboles multicaminos

• árboles B
• árboles B+

Características

• árboles binarios
• AVL
• ABB

1. Nodo padre: mínimo un elemento y max. de 2n
2. páginas intermedias, almacenar entre n (mínimo) y un max. de 2n.
3. Todas las hojas deben tener la misma altura.

ÁRBOL B+

características:

• Nodos internos solo contienen claves o apuntadores
• Todas las hojas se encuentran al mismo nivel
• Nodos hoja, se encuentran ligadas como una lista enlazada para permitir la busqueda más eficiente.
• El mínimo número de claves es 2.

operaciones:

• Buscar
• Insertar
• Eliminar

Mapa Conceptual

Para ver imagen completa presione clic Aquí ...............

Ejercicios

• Factorial

public class factorial {
private static inout io = new inout();
public static void main (String args[]) throws Exception
{
int a,m,p;a=io.readint();m=factorialrec(a);p=factorial2(a);io.writeln(m);io.writeln(p);
}
public static int factorialrec(int x)
{
int aux;aux=1;if (x==0)aux=1;else aux=aux*factorialrec(x-1);return aux;
}
public static int factorial2(int x)
{
int i,f;i=0;f=1;while (i != x)
{
i=i+1;f=f*i;}
return f;
}
}

• Fibonacci

public class Fibonacci {

public static long fib(int n)

{

if (n <= 1) return n;

else

return fib(n-1) + fib(n-2);

}

public static void main(String[] args) {

int N = Integer.parseInt(args[0]);

for (int i = 1; i <= N; i++)

System.out.println(i + ": " + fib(i));

}

}

• Algoritmo Recursivo Torres de Honoi

Hanoi (dim N , palo A, palo B , palo C)

// N, origen, destino , auxiliar

Si N == 1

Imprimir : Pasar disco de A a B

else

Hanoi(N-1 , A , C, B)

Imprimir : Pasar disco de A a B

Hanoi(N-1 , C , B , A)

Defeniciones Basicas

• Dato: Unidad mínima de información. En programación, es la expresión general que describe las características de las entidades sobre las cuales opera un algoritmo.
• Dato Abstracto (TDA/TAD/ADT): Defino un objeto, propiedad, operación y omito características del objeto como tal
• Encapsulamiento: Oculta informaión.
• Recursividad: Es una técnica de programación (puedo invocar una función).
• Recursividad Directa: Procedimiento, hay una llamada a la misma función.
• Recursividad Indirecta: Procedimiento que invoca otro procedimiento para llamar a una función.
• Recursividad Cola: Última instrucción que ejecuta el procedimiento.
• Algoritmo: Es un conjunto de instrucciones bien definidas, ordenadas y finitas de operaciones que permite hallar la solución a un problema. Dado un estado inicial y una entrada, a través de pasos sucesivos y bien definidos se llega a un estado final, obteniendo una solución.
• Pila: Se intoducen o se quitan elementos por el mismo extremo.
• Lifo: Ultimas en entrar, primeras en salir.
• Fifo: Primeras en entrar, pimeras en salir.

Estructuras Lineales

1. Lista: Conjunto de elementos llamados nodos.
2. Arreglos: Estáticos, tienen un tamaño definido.
3. Elementos Enlazados: Dinámicos, tamaño indiferente.

• Operaciones: insertar, borrado, buscar, recorrer, vacio, tamaño.
• public void insertar ( String Elemento);
• public boolean eliminar (String elemento);
• public String eliminar ();
• public boolean busacr (String elemento);
• public String recorrer ();
• public boolean vacio ();
• puiblic int tamaño ();

1. Listas Enlazadas:

• Eliminar:

1. removeFirst: elimina el primer elemento de la lista.
2. removeLast: elimina el último elemento de la lista.
3. remove: elimina un elemento concreto de la lista.

• Buscar:

1. First: examina primer elemento de la lista.
2. Last: examina el último elemento de la lista.
3. Contains: determina si la lista tiene un elemento en particular.

isEmpty: determina si la lista esta vacia.

Size: determina en número de elementos en la lista.

1. Pila: Se introducen o se quitan elementos por el mismo extremo.

• Operaciones: push, pop, peek, IsEmpty, IsFull, Size.
• Push: añadir a un elemento a la pila (apilar).
• Pop: Quitar un elemento a la pila (desapilar).
• Peek: Se mira el tope de la pila.
• IsEmpty: (Esta vacia) determinar que la pila no tiene elementos.
• IsFull: (Esta llena) determinar si la pila esta llena.
• Size: Determinar el número de elementos de la pila.