Blog. Porque programar es más que teclear

Programar árboles binarios parte 1 – Introducción / Agregar nodo

9
Pinterest
He corregido un error que había en el código, mil disculpas para quienes no les funcionaba X3 ×

Creo que uno de los mayores dolores de cabeza cuando uno estudia estructuras de datos son el programar arboles binarios de cualquier tipo, más aún cuando los programamos por ejemplo usando punteros, pero es que el mayor problema quizá es que no se entiende muy bien el funcionamiento de los arboles binarios, aqui vamos a programarlos de inicio a fin.

Contenido

  1. Introducción
  2. ¿Para que sirve un árbol binario?
  3. ¿Cómo se ingresa la información?
  4. Definición de las clases
  5. Agregar nuevo nodo al árbol
  6. Eliminar nodo del árbol
  7. Inorden, postorden, preorden (pendiente)
  8. Buscar información en el árbol (pendiente)

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:

Podemos ver en la imagen como “Raíz” es padre de “Hoja 1″ y “Hoja 2″ y estas a su vez también son la raíz de las “Sub hojas” y se vuelve un proceso recursivo hasta n cantidad de hojas.

¿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:

Si observan con detenimiento la imagen aunque se vea algo “complejo” entenderán bien el funcionamiento.

Vamos a programarlo

Todo lo dicho anteriormente, vamos a programarlo ahora usando POO con java (para que sea más fácil de entender).

Comenzamos con la abstracción de la información, tenemos que un árbol binario está compuesto por la raíz y sus nodos hijos, de la misma forma que la misma raíz no es más que otro nodo, partiendo de esto entonces crearemos 2 clases:

(Quiero comentar antes de esto que, aunque no soy muy partidario de escribir los nombres de los métodos y clases en español, por cuestiones de entendimiento para muchas personas que lleguen a esta información, los pondré de esa forma).

  • Arbol
  • Nodo

Para comenzar con esas clases tenemos, vamos ahora a definirlas:

Nodo.java

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:

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

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

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.

 

Entonces definamos nuestra función:

Podemos ver que he agregado 2 funciones para insertar un nuevo nodo, pero solo 1 de ellas es vista desde fuera, la que nosotros llamaremos, esto es porque la función que  usamos realmente para insertar (llamada dentro del método que vemos desde fuera de la clase [el método público, para quien ande perdido]) necesita una referencia de la “raíz” a partir de que nodo va a hacer las comprobaciones, para que al usar la recursividad esta raíz pueda ir cambiando (de acuerdo al algoritmo) y seguir probando y comparando nodos.

Hasta ahora hemos comprendido el funcionamiento de los árboles binarios, hemos definido las clases a usar y ya comenzamos con las funciones básicas del mismo, en la próxima entrada veremos como hacer la eliminación de un nodo para así continuar hasta terminar este tema (que tanto dolor de cabeza le da a algunas personas) tan interesante.

Pinterest
  • Pingback: Programar árboles binarios parte 2 – Eliminar Nodos

  • Franc

    No pude hacer funcionar esta función. Al código lo sigo perfectamente y tiene mucha lógica, pero al parecer no se están enlazando los nodos.

    • Mxrck

      ¿Cuál es la función que no pudiste usar?, de cualquier forma le daré una revisada, y cualquier cosa por aquí mismo te aviso y lanzo las correcciones

      • karla

        oie no seas malo por que no pones la ejecucion de como queda en total plis

        • Mxrck

          Hola amiga Karla, la verdad no entendí muy bien a que te referías, de cualquier forma puedes ver la parte 2 que es donde está la eliminación de árboles, me faltó solo los recorridos que ya tenía la entrada solo que no la he publicado.

  • naitsric

    Hola buenas una inquietud en esta linea de codigo
    public Arbol( int valor ) {
    this.raiz = new Nodo( valor );
    }
    mi clase Arbol recibe el valor que le doy verdad y el nuevo nodo toma el mismo , pero como puedo implementar para que en el proceso de addNodo se pueda ingresar el nodo con mi dato, (creo que no ingresa ni al metodo ). Seria tan amaable de solucionar esa pequeña duda ya seria mas compresible el codigo gracias.

    • Mxrck

      Buenas tardes, exacto al crear el árbol se crea su raíz con el valor que se le pase, si se quieren agregar nuevos nodos la función es:


      addNodo( Nodo nodo, Nodo raiz );

      ahora bien, de la forma en la que se hizo hay que pasar el nodo a ingresar y la “raíz” a partir de la cual se va a ingresar.

      Si se va a usar un árbol común y corriente entonces el argumento “Nodo raiz” sería la misma raíz del arbol, quedando similar a lo siguiente:


      miArbol.addNodo( new Nodo( 10 ), miArbol.getRaiz() );

      esto ingresaría el nuevo nodo a partir de la raíz del árbol.

      Un saludo.

      • Espectro

        Hola copie tu codigo tal cual por que estaba estudiando con ella pero resulta que no me funciono entonces de tanto insistir en la parte donde dice if(raiz==null){raiz = nodo} le puse this.setRaiz(nodo); y ando perfectamente no se si depronto hay problemas con la referencia la verdad yo no supe porque funciona con el setRaiz y no con raiz = nodo, pero de resto no hay problema (y)

        • Mxrck

          Amigo, tienes toda la razón y te respondo el porqué:

          Todos sabemos o pensamos (porque así nos enseñan) que los objetos en java se pasan por referencia y no por copia (a funciones), pero la realidad es que se pasa una copia que apunta a la misma referencia, lo cual significa que al hacer dentro de la función objeto = new Class(), el objeto que cambia es el que está dentro de la función y no el objeto original (*corre en circulos por el error*), así que cuando usas un método del mismo objeto, no se está creando una instancia nueva sino más bien modificando el contenido al cual hace referencia (directo en memoria).

          Muy buena observación y gracias por la corrección, de una vez lo corregiré en el código fuente.

          Saludos!!