Arboles

Introducción

Vamos a hablar primero un poco de que son los arboles binarios; nos dice Wikipedia «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», eso significa que tenemos un grafo donde cada nodo puede tener máximo 2 hijos ( o hojas ) y estas hojas no pueden tener como hijos a cualquier otra hoja anterior como podemos ver en la siguiente imagen:

¿Para que sirve un árbol binario?

Como todos sabemos un árbol binario es una estructura de datos, y como todas, este sirve para organizar datos para facilitar su manipulación, ya sea el ingreso, borrado o búsqueda de datos, y precisamente una de las principales ventajas de los árboles binarios es la búsqueda, ya que como en muchos algoritmos de búsqueda necesitamos tener la información ordenada y en nuestros árboles binarios precisamente los datos van ingresando de forma ordenada.

Recorridos con los conocidos métodos recursivos:

• Inorden
• Postorden
• Preorden

¿Cómo se ingresa la información?

Como dije anteriormente, la información se ingresa de forma ordenada esto se resuelve de forma muy sencilla con estos pasos:

1. Se toma el dato a ingresar X
2. Partiendo de la raíz preguntamos: Nodo == null ( o no existe ) ?
3. En caso afirmativo X pasa a ocupar el lugar del nodo y ya hemos ingresado nuestro primer dato.
4. En caso negativo preguntamos: X < Nodo
5. En caso de ser menor pasamos al Nodo de la IZQUIERDA del que acabamos de preguntar y repetimos desde el paso 2 partiendo del Nodo al que acabamos de visitar
6. En caso de ser mayor pasamos al Nodo de la DERECHA y tal cual hicimos con el caso anterior repetimos desde el paso 2 partiendo de este nuevo Nodo.

Nos daremos cuenta de que es un proceso RECURSIVO en el cual al final por más grande que sea el árbol el dato a entrar ocupará un lugar, vamos a ejemplificar lo ya mencionado con una imagen:

Características de los árboles

• Hijo: Es aquel nodo que siempre va a tener un nodo antecesor o padre, son aquellos que se encuentran en el mismo nivel
• Padre: Es aquel que tiene hijos y también puede tener o no antecesores.
• Hermano: Dos nodos son hermanos si son apuntados por el mismo nodo, es decir si tienen el mismo padre.
• Raíz: Es el nodo principal de un árbol y no tiene antecesores.
• Hoja o terminal: Son aquellos nodos que no tienen hijos o también los nodos finales de un árbol.
• Interior: Se dice que un nodo es interior si no es raíz ni hoja.
• Nivel de un nodo: Se dice que el nivel de un nodo es el numero de arcos que deben ser recorridos, partiendo de la raíz para llegar hasta el.
• Altura del árbol: Se dice que la altura de un árbol es el máximo de los niveles considerando todos sus nodos.
• Grado de un nodo: se dice que el grado de un nodo es el número de hijos que tiene dicho nodo.

Tipos de Árboles

• Árboles Binarios: Un árbol binario es un conjunto finito de elementos, el cual está vacío o dividido en tres subconjuntos separados: raíz del árbol, subárbol izquierdo y subárbol derecho
• Árbol de búsqueda binario auto-balanceable: Es el que intenta mantener su altura, o el número de niveles de nodos bajo la raíz, tan pequeños como sea posible en todo momento, automáticamente
• Árboles AVL: están siempre equilibrados de tal modo que para todos los nodos, la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha o viceversa.
• Árboles Rojo-Negro : Un árbol rojo-negro es un árbol binario de búsqueda en el que cada nodo tiene un atributo de color cuyo valor es rojo o negro.
• Árboles AA: utilizado para almacenar y recuperar información ordenada de manera eficiente
• Árbol de segmento: es una estructura de datos en forma de árbol para guardar intervalos o segmentos. Permite consultar cuál de los segmentos guardados contiene un punto.
• Árboles Multicamino: es un árbol ordenado cuyos nodos deben tener un número específico de hijos.
• Árboles B: Es un árbol de búsqueda que puede estar vacío o aquel cuyos nodos pueden tener varios hijos, existiendo una relación de orden entre ellos.

Recorridos de Árboles

Preorden:

1. Visitar la Raíz
2. Recorrer el subarbol izquierdo
3. Recorrer el subarbol derecho

Inorden:

1. Recorrer el subarbol izquierdo
2. Visitar la raíz
3. Recorrer el subarbol derecho

Postorden:

1. Recorrer el subarbol izquierdo
2. Recorrer el subarbol derecho
3. Visitar la raíz

Ejemplo de Código de Árboles en Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74

package pruebaarbol; import pruebaarbol.model.Nodo;   /** * * @author Daniel */ public class Pruebaarbol {     /**   * @param args the command line arguments   */   public static void main(String[] args) {       //Se asignan los valores a los nodos = 1,2,3,4,5 y 6 dentro del arbol     //Nodo raiz = 1     Nodo raiz = new Nodo(1);       //Nodo2 Izquierdo = 2     Nodo nodo2 = new Nodo(2);       //Nodo3 Derecho = 3     Nodo nodo3 = new Nodo(3);       //Se asigna el valor 6 al nodo que sera hijo del nodo 3 a la derecha     nodo3.setNodoDerecho(new Nodo(6));       //Se asigna el valor 5 al nodo que sera hijo del nodo 3 a la izquierda     nodo3.setNodoIzquierdo(new Nodo(5));       //Se asigna el valor 4 al nodo que sera hijo del nodo 4 a la izquierda     nodo2.setNodoIzquierdo(new Nodo(4));       //Se crean el Nodo 2 a la izquierda y el Nodo 3 a la derecha de la raiz     raiz.setNodoIzquierdo(nodo2);     raiz.setNodoDerecho(nodo3);       //Resultado en pantalla     System.out.println("Recorrido Preorden: ");     preOrden(raiz);     System.out.println("Recorrido Inorden: ");     inorden(raiz);     System.out.println("Recorrido PostOrden: ");     posOrden(raiz);   }     //Metodo Preorden   private static void preOrden(Nodo raiz) {     if (raiz != null) {       System.out.print(raiz.getDato() + " - ");       preOrden(raiz.getNodoIzquierdo());       preOrden(raiz.getNodoDerecho());     }   }     //Metodo Inorden   private static void inorden(Nodo raiz) {     if (raiz != null) {       inorden(raiz.getNodoIzquierdo());       System.out.print(raiz.getDato()+ " - ");       inorden(raiz.getNodoDerecho());     }   }     //Metodo PostOrden   private static void posOrden(Nodo raiz) {     if (raiz != null) {       posOrden(raiz.getNodoIzquierdo());       posOrden(raiz.getNodoDerecho());       System.out.print(raiz.getDato() + " - ");     }   }   }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

package pruebaarbol.model;   /** * * @author Daniel */ public class Nodo {   //Variables   private int dato;   private Nodo izq;   private Nodo der;     //Constructor   public Nodo(int dato){     this.dato = dato;   }   //Para saber el nodo izquierdo   public Nodo getNodoIzquierdo(){     return izq;   }   //Para saber el nodo derecho   public Nodo getNodoDerecho(){     return der;   }   //Se crea nodo derecho   public void setNodoDerecho(Nodo nodo){     der = nodo;   }   //Se crea nodo Izquierdo   public void setNodoIzquierdo(Nodo nodo){     izq = nodo;   }     public int getDato(){     return dato;   } }

PROGRAMACIÓN EN JAVA

• Arbol
• Nodo

Nodo.java

public class Nodo {

    /* Declaraciones de variables */

    private int valor;

    private Nodo padre;

    private Nodo hojaIzquierda;

    private Nodo hojaDerecha;

    /* Constructor */

    public Nodo(int valor) {

        this.valor = valor;

    }

    /* Setters y Getters */

    public void setValor(int valor) {

        this.valor = valor;

    }

    public int getValor() {

        return valor;

    }

    public Nodo getPadre() {

        return padre;

    }

    public void setPadre(Nodo padre) {

        this.padre = padre;

    }

    public Nodo getHojaIzquierda() {

        return hojaIzquierda;

    }

    public void setHojaIzquierda(Nodo hojaIzquierda) {

        this.hojaIzquierda = hojaIzquierda;

    }

    public Nodo getHojaDerecha() {

        return hojaDerecha;

    }

    public void setHojaDerecha(Nodo hojaDerecha) {

        this.hojaDerecha = hojaDerecha;

    }

}

Vamos a revisar un poco más de cerca el código.

Es una clase muy sencilla, como podemos ver únicamente tiene 4 atributos (variables) fáciles de entender:

• valor
• hojaIzquierda
• hojaDerecha

valor es el dato almacenado del propio nodo, mientras que como recordaremos cada nodo puede tener máximo 2 hijos uno a la izquierda y otro a la derecha, donde todos los nodos a su izquierda son menores a el mismo y todos los nodos a su derecha son mayores a el mismo, pero que comienzan como nulos ya que al crear un nuevo nodo, este no tiene hijos.

Hay que tener cuidado con setValor( int valor ) ¿Porque? pues bien, no podemos actualizar el valor al aire ya que perderíamos el orden, por lo que tenemos un contructor:

    /* Constructor */

    public Nodo(int valor) {

        this.valor = valor;

    }

a partir del cual se ingresa el valor del nodo al crear una instancia del mismo:

Nodo nodo = new Nodo( 1 );

Ya tenemos nuestra clase nodo lista, ahora pasemos con la clase Arbol.java que es aún más sencilla ( en definición ) que Nodo:

Arbol.java

public class Arbol {

    /* Atributos */

    private Nodo raiz;

    /* Contructories */   

    public Arbol( int valor ) {

        this.raiz = new Nodo( valor );

    }

    public Arbol( Nodo raiz ) {

        this.raiz = raiz;

    }

    /* Setters y Getters */

    public Nodo getRaiz() {

        return raiz;

    }

    public void setRaiz(Nodo raiz) {

        this.raiz = raiz;

    }

}

Prácticamente por ahora lo importante es su atributo «raiz» del tipo Nodo, el cual representará a todo nuestro árbol, adicionalmente he creado constructores que pueden ser de ayuda al momento de inicializar el árbol para crear la raíz de paso.

pffff que nos hemos alargado con el post, pero aún no terminamos, acabamos apenas de definir entidades faltan todas las funciones del mismo. vamos con ellas.

Hay que agregar métodos a nuestra clase de Arbol para poder ingresar nuevos nodos:

• addNodo
• removeNodo
• recorridoPreorden
• recorridoInorden
• recorridoPostorden

Programando las funciones del árbol

En esta primera parte quiero abarcar al menos hasta el ingreso de nuevos nodos, comencemos entonces.

La modificación la haremos en nuestra clase Arbol que es la que llevará estas funciones de control, recordemos nuestro algoritmo de inserción que planteamos anteriormente:

1.     Se toma el dato a ingresar X

2.     Partiendo de la raíz preguntamos: Nodo == null ( o no existe ) ?

3.     En caso afirmativo X pasa a ocupar el lugar del nodo y ya hemos ingresado nuestro primer dato.

4.     En caso negativo preguntamos: X < Nodo

5.     En caso de ser menor pasamos al Nodo de la IZQUIERDA del que acabamos de preguntar y repetimos desde el paso 2 partiendo del Nodo al que acabamos de visitar

6.     En caso de ser mayor pasamos al Nodo de la DERECHA y tal cual hicimos con el caso anterior repetimos desde el paso 2 partiendo de este nuevo Nodo.

IMAGENES

                                                                         VIDEOS