Arboles Binarios

Definición de teoría de grafos
[pic]

Un árbol binario sencillo de tamaño 9, 4 niveles y altura 3 (altura = máximo nivel - 1), con un nodo raíz cuyo valor es 2.
En teoría de grafos se usa la siguiente definición: «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 árbolbinario 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 rehusamos 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 esun á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 laderecha como hijo derecho.

Recorridos sobre árboles binarios


Recorridos en profundidad

El método de este recorrido es tratar de encontrar de la cabecera a la raíz en nodo de unidad binaria. Ahora pasamos a ver la implementación de los distintos recorridos:
Recorrido en pre orden
En este tipo de recorrido se realiza cierta acción (quizás simplemente imprimir por pantalla el valor de laclave de ese nodo) sobre el nodo actual y posteriormente se trata el subárbol izquierdo y cuando se haya concluido, el subárbol derecho. Otra forma para entender el recorrido con este método seria seguir el orden: nodo raíz, nodo izquierdo, nodo derecho.
En el árbol de la figura el recorrido en pre orden sería: 2, 7, 2, 6, 5, 11, 5, 9 y 4.
Recorrido en post orden
En este caso se trata primero elsubárbol izquierdo, después el derecho y por último el nodo actual. Otra forma para entender el recorrido con este método seria seguir el orden: nodo izquierdo, nodo derecho, nodo raíz. En el árbol de la figura el recorrido en post orden sería: 2, 5, 11, 6, 7, 4, 9, 5 y 2.
Recorrido en in orden
En este caso se trata primero el subárbol izquierdo, después el nodo actual y por último el subárbolderecho. En un ABB este recorrido daría los valores de clave ordenados de menor a mayor. Otra forma para entender el recorrido con este método seria seguir el orden: nodo izquierdo, nodo raíz, nodo derecho. En el árbol de la figura el recorrido en in orden sería: 2, 7, 5, 6, 11, 2, 5, 4, 9.

Árbol binario Java (para números no repetidos)

Clase NodoArbol

package ejemploarbolb;

/**
*
*@author Carlos
*/
public class NodosArbol {
//datos amigables para que la clase lista tenga un acceso directo
Object datos;
NodosArbol izquierdo;
NodosArbol derecho;
//Constructor crea un nodo de tipo Object
NodosArbol(Object valor)
{
datos=valor;
izquierdo = null;
derecho = null;
}
//Constructor Creaun nodo de tipo Object y al siguiente nodo de la lista
NodosArbol (Object valor,NodosArbol izqnodo,NodosArbol dernodo){
datos = valor;
izquierdo = izqnodo;
derecho = dernodo;
}
//Retorna el dato que se encuentra en ese nodo
}

Clase ArbolB

package ejemploarbolb;

/**
*
* @author Carlos
*/
public class ArbolB
{
NodosArbol raiz;...