Qué es un árbol
Un árbol se define como una colección de nodos donde cada uno además de almacenar información, guarda las direcciones de sus sucesores.
Los árboles representan las estructuras no-lineales y dinámicas de datos más importantes en computación.
- Dinámicas, puesto que la estructura árbol puede cambiar durante la ejecución de un programa.
- No- lineales puesto que a cada elemento del árbol pueden seguirle varios elementos.
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:
- Visitar la Raíz
- Recorrer el subarbol izquierdo
- Recorrer el subarbol derecho
Inorden:
- Recorrer el subarbol izquierdo
- Visitar la raíz
- Recorrer el subarbol derecho
Postorden:
- Recorrer el subarbol izquierdo
- Recorrer el subarbol derecho
- 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; } } |
¿Te gustó este artículo?
Si te gustó este artículo, te ha servido o aprendiste algo nuevo; compártelo en tus redes sociales o invítame un cafe.
Excelente aporte
Muy bueno :’)
Ola ..muy buena informacion …tienes canal en youtube para seguirte?
Si, pero no tiene mucho contenido y tampoco le invierto tiempo en la edición.
https://www.youtube.com/channel/UCSrjHaBRa1m-04bPEgzhGBQ
Aún así, espero que te sirva.
La implementación de la idea de un árbol es muy burda ya que tu haces las relaciones de manera manual, no es un código que permita posicionar un elemento en base a una condición. Hay que ser mas cuidadoso en subir ejemplos porque cualquier programador novato podría haberse ido con la finta. Este código no es un buen ejemplo del algoritmo para crear un árbol.
al chile
Pues proponga el programa usted hijueputa, malparido, gonorrea, treinta pirobo