arbolbb.visitarPosorden();
System.out.println("\nArbol preorden: ");
arbolbb.visitarPreorden();
Este blog ha sido creado para compartir nuestras enseñanzas en la red.
Un árbol binario es un grafo conexo, acíclico y no dirigido tal que el grado de cada vértice no es mayor a 3». De esta forma sólo existe un camino entre un par de nodos.
Un árbol binario con enraizado es como un grafo que tiene uno de sus vértices, llamado raíz, de grado no mayor a 2. Con la raíz escogida, cada vértice tendrá un único padre, y nunca más de dos hijos. Si reusamos el requerimiento de la conectividad, permitiendo múltiples componentes conectados en el grafo, llamaremos a esta última estructura un bosque.
Tipos de árboles binarios
Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos.
Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.
Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con cero hijos) están a la misma profundidad (distancia desde la raíz, también llamada altura)
A veces un árbol binario perfecto es denominado árbol binario completo. Otros definen un árbol binario completo como un árbol binario lleno en el que todas las hojas están a profundidad n o n-1, para alguna n.
Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.
ARBOL AVL
PROGRAMA ARBOLES B+
public class BTree {
private BTree izquierda= null;
private BTree derecha= null;
private Object elemento;
public static int LADO_IZDO= 1;
public static int LADO_DRCHO= 2;
public BTree(Object elemento) {
this.elemento = elemento ;
}
public Object getElement() {
return elemento;
}
public BTree getIzquierda() {
return izquierda;
}
public BTree getDerecha() {
return derecha;
}
public void insertar(BTree tree, int lado) throws BTreeException {
if (lado==LADO_IZDO) {
if (izquierda==null) izquierda= tree;
else throw new BTreeException("Ya hay un ?rbol enlazado");
}
else if (lado==LADO_DRCHO) {
if (derecha==null) derecha= tree;
else throw new BTreeException("Ya hay un ?rbol enlazado");
}
else throw new BTreeException("Lado incorrecto");
}
public BTree extraer(int lado) throws BTreeException {
BTree subarbol;if (lado==LADO_IZDO) {
subarbol= izquierda;
izquierda= null;
}
else if (lado==LADO_DRCHO) {
subarbol= derecha;
derecha= null;
}
else
throw new BTreeException("Lado incorrecto");
return subarbol;
}
public void imprimePreOrden() {
System.out.println(elemento);
if (izquierda!=null) izquierda.imprimePreOrden();
if (derecha!=null) derecha.imprimePreOrden();
}
public void imprimePostOrden() {
if (izquierda!=null) izquierda.imprimePostOrden();if (derecha!=null) derecha.imprimePostOrden();System.out.println(elemento); } public void imprimeEnOrden() {if (izquierda!=null) izquierda.imprimeEnOrden();System.out.println(elemento);if (derecha!=null) derecha.imprimeEnOrden(); }}*****************public class BTreeException extends Exception { public BTreeException (String mensaje) {super(mensaje); }}******************public class Trabalenguas { public static void main(String args[]) {BTree trabalenguas, subarbol, temporal;try { trabalenguas= new BTree("Tres"); subarbol= new BTree("tristes"); trabalenguas.insertar(subarbol, BTree.LADO_IZDO); temporal= new BTree("tigres"); trabalenguas.insertar(temporal, BTree.LADO_DRCHO); temporal= new BTree("com?an"); subarbol.insertar(temporal, BTree.LADO_IZDO); temporal= new BTree("trigo"); subarbol.insertar(temporal, BTree.LADO_DRCHO);} catch (BTreeException ex) { System.out.println(ex.getMessage()); return;}trabalenguas.imprimePreOrden();System.out.println("------------------");trabalenguas.imprimeEnOrden();System.out.println("------------------");trabalenguas.imprimePostOrden();System.out.println("------------------");System.out.println("------------------");try { subarbol= trabalenguas.extraer(BTree.LADO_IZDO);} catch (BTreeException ex) { System.out.println(ex.getMessage()); return;}trabalenguas.imprimePreOrden(); }}
CODIGO EN JAVA DE COLAS
public void inserta(Elemento x) {
Nodo Nuevo;
Nuevo=new Nodo(x, null);
if (NodoCabeza==null)
NodoCabeza=Nuevo;
else
NodoFinal.Siguiente=Nuevo;
NodoFinal=Nuevo;
}
public Elemento cabeza()throws IllegalArgumentException {
if (NodoCabeza == null) throw new IllegalArgumentException();
else return NodoCabeza.Info;
}
public Cola(){
// Devuelve una Cola vacía
NodoCabeza=null;
NodoFinal=null;
}
Tipos de Colas
Colas circulares (anillos): en las que el último elemento y el primero están unidos. Colas de prioridad: En ellas, los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen. Hay 2 formas de implementación:
Añadir un campo a cada nodo con su prioridad. Resulta conveniente mantener la cola ordenada por orden de prioridad.
Crear tantas colas como prioridades haya, y almacenar cada elemento en su cola.
Bicolas: son colas en donde los nodos se pueden añadir y quitar por ambos extremos; se les llama DEQUE (Double Ended QUEue). Para representar las bicolas lo podemos hacer con un array circular con Inicio y Fin que apunten a cada uno de los extremos. Hay variantes: Bicolas de entrada restringida: Son aquellas donde la inserción sólo se hace por el final, aunque podemos eliminar al inicio ó al final.
Bicolas de salida restringida: Son aquellas donde sólo se elimina por el final, aunque se puede insertar al inicio y al final.
Un árbol consiste en un conjunto de nodos y un conjunto de aristas, de forma que se puede distinguir un nodo llamado raíz
· A cada nodo h, excepto la raíz, le llega una arista de otro nodo p (p padre de h, h uno de los hijos de p).
· Para cada nodo hay un camino (secuencia de aristas) único desde la raíz.
· Existe un orden lineal para todos sus hijos.
· Un árbol binario es un árbol ordenado, en el que cada nodo tiene 0, 1 o 2 hijos (el hijo izquierdo y el derecho).
Un camino de un nodo a otro, es una secuencia de aristas consecutivas que llevan del primero al segundo. Su longitud es el número de aristas que tiene.
La profundidad de un nodo es la longitud del camino de la raíz a ese nodo.
La altura de un árbol es la profundidad del nodo más profundo.
Factor de equilibrio
Cada nodo, además de la información que se pretende almacenar, debe tener los dos punteros a los árboles derecho e izquierdo, igual que los arboles binarios de busqueda (ABB), y además el dato que controla el factor de equilibrio.
El factor de equilibrio es la diferencia entre las alturas del árbol derecho y el izquierdo:
FE = altura subárbol derecho - altura subárbol izquierdo;
Por definición, para un árbol AVL, este valor debe ser -1, 0 ó 1.
Si el factor de equilibrio de un nodo es:
0 -> el nodo está equilibrado y sus subárboles tienen exactamente la misma altura.
1 -> el nodo está equilibrado y su subárbol derecho es un nivel más alto.
-1 -> el nodo está equilibrado y su subárbol izquierdo es un nivel más alto.
Si el factor de equilibrio Fe≥2 o Fe≤-2 es necesario reequilibrar.
Recorrido preorden