Download Clases #18

Clases #18
01/diciembre/2014
Arboles binarios
Cada nodo tiene dos hijos
Aplicación: representa y evolución de expresiones aritmética. Búsqueda y ordenamiento.
Terminología: Dos subárboles diferenciados en cada nodo (inclinaciones).
Completo: cada nodo tiene dos o ceros descendientes, la figura anterior no es yn árbol binario
completo.
Balanceado: para cada nodo la diferencia entre las alturas de subDer y SubIzq debe ser menor
que dos.
Degenerado: cada nodo solo tiene un hijo, excepto la hoja.
Lleno: cada nivel tiene el máximo de nodos que soporta.
Ejemplo donde podemos presenciar si es un árbol binario, completo, balanceado, degenerado o
lleno
Arboles
Completo
Lleno
Degenerado
Balanceado
A
X
X
B
X
X
X
C
X
X
✓
✓
✓
X
✓
✓
X
✓
✓
D
Notas:
En el balanceado si la diferencia de niveles es mayor a entonces no está balanceado, para
determinar si un árbol esta balanceado está lleno se cumple esta formulas 2ℎ -1 donde h es el
nivel del árbol.
Implementación
Se puede implementar tanto en arreglos o nodos.
Codigo java - 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;
}
}