Arboles Binarios.

1. Definición: Arboles que tienen máximo dos hijos por nodo.

2. Terminología: máximo dos hijos que se distingue entre izquierdo y derecho.

Figura numero 15

• Completo: todos los nodos o tienen dos hijos o cero.
• Lleno: todos los niveles tienen el máximo de nodos y se calcula por medio de la formula 2^n -1. donde n es altura.
• Degenerado: todos los nodos solo tienen un hijo excepto la hoja.
• Balanceado: en todos los nodos la diferencia entre las alturas del subárbol   izquierdo y derecho es menor que 2 y mayor que -2. 

  Ejemplos:

Se tienen los siguientes Arboles:

Árbol	A	B	C	D
Completo	x	x	ü	ü
Lleno	x	x	x	ü
Degenerado	x	ü	x	ü
Balanceado	ü	x	ü	ü

Después de analizar pude concluir que todo árbol binario que sea lleno es por consiguiente completo, pero todo árbol completo no necesariamente tiene que ser lleno.  

3. Implementacion

  

        3.1 Estática (Arreglos)

              

           

Figura numero 16

En la imagen se ilustra un árbol el cual es implementado con arreglos, resulta necesario declarar tres arreglos el primero es de tipo T que guardara los datos que tiene el árbol, el segundo es de tipo int que almacena la posición en que están almacenados los datos que se encuentran en el árbol  del  lado izquierdo, el tercero también cumple la función del segundo pero en este se guardan los del lado derecho.

  3.2 Dinámica (Nodos)

  

Figura numero 17

   En esta imagen se muestra el árbol que aparece en la figura numero 16 con la implementacion en nodos donde se declara una variable raíz el cual apunta al primero nodo del árbol.

Clase NodoArbolBin.

public class NodoArbolBin <T> {

private T dato;

private NodoArbolBin izq;

private NodoArbolBin der;

public NodoArbolBin (T dato){

this.dato=dato;

izq=der=null;

}

public NodoArbolBin(T dato, NodoArbolBin izq, NodoArbolBin der){

  

  this.dato=dato;

   this.izq=izq;

   this.der=der;

}

public T getDato(){ return dato;}

public NodoArbolBin getIzq() { return izq;}

public NodoArbolBin getDer(){ return der;}

public void setIzq(NodoArbolBin izq){

this.izq=izq;

}

public void setDer(NodoArbolBin der){

this.der=der;

}

}

public class Principal {

  public static void main (String ae []){

  NodoArbolBin raiz= new NodoArbolBin ("A");

  raiz.setIzq(new NodoArbolBin("B"));

  raiz.setDer(new NodoArbolBin("C"));

 NodoArbolBin p = raiz.getIzq();

p.setIzq(new NodoArbolBin("D"));

p= raiz.getDer();

p.setIzq(new NodoArbolBin("E"));

p.setDer(new NodoArbolBin("F"));

preOrden(raiz);

}

public static void preOrden(NodoArbolBin r){

  if(r!=null){

 System.out.println(r.getDato());

   preOrden(r.getIzq());

  preOrden(r.getDer());

}

}

}

 Apreciaciones Importantes y Reflexión.

En la figura numero 16 los arreglos izq y der donde aparecen el -1 quiere decir que no tiene hijos de ese lado ya sea tanto izquierdo como derecho.

En la figura numero 17 el árbol realizado con nodos cuando en la parte izq o der tenga almacenado un null quiere decir que no tiene hijos de ese lado.  

Logre aprender sobre otra clase de árbol  sus terminologias y sus  implementaciones, con base a las gráficas se paso a realizar la clase NodoArbolBin.

Una conclusión muy importante es que todo árbol degenerado solo tiene un hijo.

Arboles.

1. Definición: Estructura de datos no lineales para organizar la información por niveles.

2. Utilidad: Organizar datos en estructuras jerárquicas (se diferencia entre elementos mayores y menores).

3. Aplicaciones: Las aplicaciones de los arboles pueden ser: organigrama, genealogía, directorios, expresiones aritméticas, ordenamiento y búsqueda.

4. Terminología : 

                           Árbol General:  compuesto por nodos que pueden tener una cantidad indeterminada de                                 descendientes.

     

                           

Figura numero 12

Niveles: determinados por la posición horizontal de los nodos, en el árbol anterior ay tres niveles el nodo de color amarillo es un nivel, los nodos de color azul es el segundo nivel, y los nodos de color rojo es el tercer nivel.  

Altura: cantidad de niveles (3).

peso: cantidad de hojas (7).

Implementacion.

Aprendimos en la clase dos maneras de realizar la implementacion de arboles, como son: 

1.  Estática (arreglos). 

Para la implementacion con arreglos es necesario tener dos vectores uno que guarde los datos y otro que almacene la posición del padre del dato por ejemplo se tiene el siguiente árbol:

Figura numero 13

2. Dinámicas (Nodos).

Para realizar la implementacion de un árbol con nodos a este se le debe realizar un cambio el cual se muestra en la figura numero 13.

Figura numero 14

Para realizar el árbol que se encuentra en la figura numero 13 con la implementacion de nodos se realiza de la siguiente manera.

Donde la variable r es la raíz. 

Apreciaciones importantes y Reflexión.

En la clase logramos aprender sobre una estructura de datos no lineal llamada árbol, pude llegar a la conclusión que de las dos implementaciones vistas la mas opcionada para mi opinión es la implementacion con nodos  porque se puede decir que la memoria no quedara el árbol corto, si en caso de que la implementacion sea con arreglos al momento que se llegue a la cantidad máxima de este no se podrá añadir mas información al árbol.

Recursividad 

Aplicaciones.

Las aplicaciones donde se pueden aplicar la  recursividad son:

Recorrido de estructuras no lineales

Formulas matemáticas: se puede aplicar la  recursividad en un algoritmo para una formula matemática donde el proceso iterativo es muy complejo un ejemplo de estos algoritmos es:

Crear una función en java donde se pueda calcular el factorial de un numero entero mayor o igual a cero.

Las  funciones recursiva son realizadas de la siguiente manera.
acceso modificador tipo/clase nombreMetodoRecursivo (parámetros) {
      if(condición para detener autollamado)
       // instrucciones
       nombreMetodoRecursivo (argumentos); // autollamado
}

Para realizar esta función o método debemos tener en cuenta que el factorial de un numero es otro numero que resulta de la siguiente formula n!=n*(n-1)! donde n es el numero y el carácter "!" tiene como significado factorial mediante un ejemplo tendremos mas claridad sobre el factorial. ejemplo: factorial de 5 : 5! = 5*4!   4!=4*3!;  3!=3*2!;  2!=2*1!;  1!=1*0!;  0!=1.

Remplazando cada factorial tenemos que 1!=1*0! = 1;  2!= 2*1! = 2;  3!=3*2!= 6;  4!=4*3!=24;  5! = 5*4! = 120. Como resultado final obtenemos 120, quiere decir que el factorial de 5 es 120.

Analizando el  método recursivo mediante la siguiente figura.

Figura numero 11

La pila anterior ilustrada en la Figura numero 11 es la que almacena las instrucciones pendientes por realizar, la primera llamada del método realizada en el método main fue de 5 este quedo a la espera del llamado que ahora se realizo con (num-1) y así con las demás llamadas hasta que n valga cero y retorne 1 para luego realizar las instrucción pendientes que se encuentran en la pila interna del sistema operativo.

Ejercicios, funciones recursivas para:
1. calcular potenciacion entre dos numero naturales.
2. mostrar los elementos de una lista enlazada simple (invertida).

En la clase anterior se muestran los dos métodos el primero es casi igual al ejemplo de el factorial siendo que   recibe dos parámetros el cual uno es la base y el otro es el exponente. El segundo método recibe una lista y no retorna,  lo que primero que se hace es poner la condición del autollamado y en la pila se van guardando las instrucción que quedan pendiente como son el System.out.println() de cada dato que tiene la lista, cuando termina el autollamado la pila interna del sistema operativo realiza las instrucciones que tiene almacenada.  

Apreciaciones importantes y reflexión.

Como se pudo dar cuenta en el  método recursivo anterior nos facilita la solución una formula matemática, y en pocas lineas de código, que realizada iterativa mente resultaría un poco mas compleja. Recordemos que los métodos recursivo tienen considerable consumo de memoria.