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.