En este caso vamos a estudiar estructuras no lineales como son los árboles, estudiaremos su definición y su terminología.
Los árboles en informática son un conjunto finito de elementos a los cuales denominamos nodos, los cuales están conectados por líneas dirigidas las cuales se denominan ramas.
Importancia
Como todos sabemos un árbol 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, la ventaja es que las búsquedas se realiza con mucha eficiencia ya que el árbol se ingresa de manera ordenada.
TERMINOLOGIA DE ARBOLES
- El primer nodo(A) Se llama raíz.
- Se llama nodo padre si tiene sucesores. “E” no es nodo padre.
- Los hijos del nodo raíz están en el nivel 1. Y el nodo raíz en el nivel 0.
- Los nodos sucesores se llaman hijos.
- Dos o más nodos con el mismo padre se llaman hermanos como C y D.
- Amplitud es el nivel más poblado. En el ejemplo es el nivel (2)
- Un nodo sin hijos se denomina hoja.
- EL nivel de un nodo es la distancia al nodo raíz.
- La profundidad o altura es la longitud del camino más largo que conecta la raíz con una hoja.
ÁRBOL BINARIO
Los arboles binarios son estructuras recursivas, en este caso cada nodo puede tener de cero a dos hijos. Los arboles binarios se dividen en tres partes el nodo raiz, el subárbol derecho y el izquierdo.
Lo más importante es conocer los recorridos de estos árboles, existen dos formas de recorrer en anchura y profundidad.Los recorridos consisten en visitar un nodo una sola vez. idos consisten en visitar un nodo una sola vez.
Recorridos:
PREORDEN (NID) : Primero se procesa la raíz, a continuación, el subárbol izquierdo y, posteriormente, el subárbol derecho.
1. Visitar el nodo raíz (N)
2. Recorrer el subárbol izquierdo (I) en preorden.
3. Recorrer el subárbol derecho (D) en preorden.
EN ORDEN (IND) : Procesa primero el subárbol izquierdo, después el raíz y, a continuación, el subárbol derecho.
1. Recorrer el subárbol izquierdo (I) en orden.
2. Visitar el nodo raíz (N).
3. Recorrer el subárbol derecho (D) en orden
POSTORDEN (IDN): El recorrido postorden (IDN) procesa el nodo raíz (post) después de que los subárboles izquierdo y derecho se hayan procesado.
1. Recorrer el subárbol izquierdo (I) en postorden.
2. Recorrer el subárbol derecho (D) en postorden.
3. Visitar el nodo raíz (N).
Ejemplo:
1. Niveles: 5
2.Altura: 5+1=6
3.Grado: 2 en el nodo A, B, D, L. El nodo N y J tienen grado 1
4.Representación en una lista: A(B(E,F(L(M,(N(O))))D(I,J(K))))
5. Nodos hoja: (E,M,O,I,K)
6. Caminos que conducen a hojas: Camino a hoja E: (A, B, E) Camino a hoja M: (A, B, F, L, M) Camino a hoja O: (A, B, F, L, N, O) Camino a hoja I: (A, D, I) Camino a hoja K: (A, D, J, K)
7. Amplitud: La amplitud está en el nivel 2 y es 4.
8. Hijos de nodo N: (O) y sus ancestros (L,F,B,A)
9. El árbol está equilibrado o perfectamente equilibrado: Esta equilibrado en el nivel 2.
10. El nodo raíz: A
11. Nodos padres: (A,B,L,N,D,J)
12. Hermanos del nodo E : ( F,I,J)
13. Recorridos:
Implementación:
Creación de nodo del Árbol Binario:
Comenzaremos creando el nodo del árbol, esto se lo ha realizado dentro del paquete entidades.
Creamos la clase NodoArbol que es la que se utiliza para crear punteros izquierdos y derecho del árbol además de tener la información del árbol que en este caso es de tipo entero.
package Entidades;
import Controladores.ArbolBinario;
//Nombre de la clase
public class NodoArbol {
public int info;//Dato tipo entero
public ArbolBinario izq, der;//punteros del arbol
//Constructor
public NodoArbol(int info) {
this.info = info;//Se inicializa info con la informacion del
this.izq = null;//parametro del constructor
this.der = null;
}
//Constructor sin parametros
public NodoArbol() {
this.info = 0;//se inicializa la informacion del arbol con 0
this.izq = null;//puntero izquierdo apunta null
this.der = null;//puntero derecho apunta null
}
}
Creación de la clase ArbolBinario:
Para la implementación de esta clase tenemos que tener en cuenta que la parte más importante en la raíz, la cual se utiliza en todas las operaciones de la clase.
package Controladores;
import Entidades.NodoArbol;
public class ArbolBinario {
//Dato
public NodoArbol raiz;
public ArbolBinario() {
this.raiz = null;
}
Método estaVacia:
//Comprueba si esta vacio
public boolean estaVacia() {
return (raiz == null);
}
Ingresar Nodos al árbol:
El ingreso utiliza un método recursivo al momento de almacenar los datos ya sea a la derecha o izquierda, se lo hace mediante una condición de ingreso.
Pasos de inserción:
1. Se toma el dato info.
2. está vacío se crea un nuevo nodo, y se inserta el info en el nodo, se crean los punteros derecho e izquierdo, se declara a raíz como nuevo.
3. En caso de no estar vacío, pregunta si info es mayor a raíz.
4. 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.
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.
public void insertar(int info) {
if (estaVacia()) {
NodoArbol nuevo = new NodoArbol();//Creacion de un nuevo nodo
nuevo.info = info;//se inserta un nuevo nodo
nuevo.der = new ArbolBinario();//inicializa puntero derecho
nuevo.izq = new ArbolBinario();//inicializa puntero izquierdo
raiz = nuevo;
} else {
if (info > raiz.info) { //Criterio de insercción
(raiz.der).insertar(info);//se inserta a la derecha
}
if (info < raiz.info) {
(raiz.izq).insertar(info);//se inserta a la izquierda
}
}
}
RECORRIDOS: Existen tres tipos de recorrido, para su implementación utilizamos la recursividad, ya que es muy eficiente en este caso, podemos darnos cuenta que lo que cambia en cada recorrido es el orden de la impresión de la información.
//Recirrido en preOrden R-I-D
public void preOrden() {
if (!estaVacia()) {
System.out.print(raiz.info + " ");
raiz.izq.preOrden();
raiz.der.preOrden();
}
}
//Recorrido en orden I-R-D
public void enOrden() {
if (!estaVacia()) {
raiz.izq.enOrden();
System.out.print(raiz.info + " ");
raiz.der.enOrden();
}
}
//Recorrido post orden I-D-R
public void posOrden() {
if (!estaVacia()) {
raiz.izq.posOrden();
raiz.der.posOrden();
System.out.print(raiz.info + " ");
}
}
Contar la cantidad de nodos: Este método cuenta la cantidad de nodos que posee el árbol recorre recursivamente los nodos izquierdos y derechos contándolos y la condición de parada es que este vacío.
public int cantidad() {
if (estaVacia()) {
return 0;
} else {
return (1 + raiz.der.cantidad() + raiz.izq.cantidad());
}
}
Altura del árbol
public int altura() {
if (estaVacia()) {
return 0;
} else {
return (1 + Math.max(raiz.der.altura(), raiz.izq.altura()));
}
}
Encontra el valor mayor y menor:Para este método tenemos la ventaja de que el árbol tiene a la izquierda los datos menores y la dercha los mayores. Lo que este hace es recorrer todos los nodos de la derecha hasta encontrarse con el mayor y lo retorna lo mismo hace con los nodos de la izquierda. Se ha utilizado una instrucción de excepciones, en caso de encontrar un error el programa no se caerá.
//Buscar Nodo menor
public int buscarMin() {
ArbolBinario actual = this;
int devuelvo = -1;
try {
while (!actual.raiz.izq.estaVacia()) {//mientras no este vacio
actual = actual.raiz.izq;//recorre hasta el ultimo nodo izquierdo
}
devuelvo = actual.raiz.info;//valor se incializa con el valor menor
} catch (Exception e) {
actual.raiz = null;
return devuelvo;
}
return devuelvo;
}
//Buscar Nodo mayor
public int buscarMax() {
ArbolBinario actual = this;
int devuelvo = -1;
try {
while (!actual.raiz.der.estaVacia()) {//mientras no este vacio
actual = actual.raiz.der;//recorre hasta el ultimo nodo derecho
}
devuelvo = actual.raiz.info;//valor se incializa con el valor mayor
} catch (Exception e) {
actual.raiz = null;
return devuelvo;
}
return devuelvo;
}
Verificar si el nodo es hoja:
Tenemos que tener en claro que los nodos hojas son aquellos que no tienen hijos. Por lo cual los punteros tienen que estar apuntando a null.
Como podemos ver si retorna true (verdadero) en nodo es hoja debido a la condición donde verifica que los punteros izquierdo y derecho están vacíos.
//Verficar si el Nodo es Hoja
public boolean esHoja() {
boolean hoja = false;
if ((raiz.izq).estaVacia() && (raiz.der).estaVacia()) {
hoja = true;
}
return hoja;
}
Buscar un nodo:
Este método busca un dato ingresado, lo que hace es preguntar si esta no está vacío, si es afirmativo pregunta si el dato ingresado es igual a la raíz retorna el mismo dato ingresado, caso contrario preguntara si dato ingresado en menor a la raíz de ser afirmativo recorrerá de forma recursiva a la izquierda buscando el dato, caso contrario recorre a la derecha. Si el dato existe retornara.
//Buscar Nodo segun un dato
public ArbolBinario buscar(int a) {
ArbolBinario arbol = null;
if (!estaVacia()) {
if (a == raiz.info) {
return this; //retorna el dato encontrado
} else {
if (a < raiz.info) {//busca a la izquierda
arbol = raiz.izq.buscar(a); //Recursividad
} else {//busca a la derecha
arbol = raiz.der.buscar(a); //Reursividad
}
}
}
return arbol;
}
Eliminar un Nodo: Este método es complicado debido a que el nodo que se elimina puede ser un nodo padre o el nodo raíz, de ser así el nodo que lo remplazado por uno de sus hijos. Este método utiliza el buscar nodo ya que para poder ser eliminado un nodo se debe encontrar.
//Eliminar Nodo
public void eliminar(int a) {
try {
ArbolBinario eliminado = buscar(a);//Busca el dato a
if (!eliminado.estaVacia()) {//verifica si no esta vacio
if (eliminado.esHoja()) {//verifica si es hoja
eliminado.raiz = null;//elimina la hoja
} else {//si los punteros derecho e izquierdo no estan vacios
if (!eliminado.raiz.izq.estaVacia() && !eliminado.raiz.der.estaVacia()) {
int b = eliminado.raiz.der.buscarMin();//busca el dato menor derecho
ArbolBinario temp = buscar(b);
temp.raiz = temp.raiz.der.raiz;
eliminado.raiz.info = b;
} else {
if (eliminado.raiz.izq.estaVacia()) {//verifica si rama izquierda esta vacia
eliminado.raiz = eliminado.raiz.der.raiz;
} else {
eliminado.raiz = eliminado.raiz.izq.raiz;
}
}
}
}
} catch (Exception e) {
e.getMessage();
}
}
Editar un Nodo:
Este método simplemente lo que hace eliminar un nodo e ingresar otro en el mismo punto que se eliminó, por lo tanto lo que se hace es llamar al método eliminar e insertar un nuevo nodo.
public void editar(int dato, int nuevo) {
eliminar(dato);
insertar(nuevo);
}
Método main
package Vistas;
import Controladores.ArbolBinario;
public class Vistas {
public static void main(String[] args) {
ArbolBinario a = new ArbolBinario();//Se invoca la clase
//Ingreso de datos
a.insertar(50);
a.insertar(10);
a.insertar(5);
a.insertar(15);
a.insertar(7);
a.insertar(3);
a.insertar(57);
// a.insertar(8);
// a.insertar(6);
// a.insertar(150);
//Recorridos
System.out.println("\nPreOrden");
a.preOrden();
System.out.println("\nEnOrden");
a.enOrden();
System.out.println("\nPosOrden");
a.posOrden();
System.out.println("\nAltura: " + a.altura());
System.out.println("Cantidad de nodos: " + a.cantidad());
System.out.println("Minimo: "+a.buscarMax());
System.out.println("Maximo: "+a.buscarMin());
int dato = 10;
//Buscar Nodo
String encontrado = a.buscar(dato) != null ? "Encontrado" : "No encontrado";
System.out.println("Dato "+dato+": "+encontrado);
a.eliminar(dato);//Se eliminara el dato 50
System.out.println("editar 10 x 140");
a.editar(10, 140);//Se cambiara el 10 por el 140
System.out.println("PreOrden");
a.preOrden();
System.out.println("\nEnOrden");
a.enOrden();
System.out.println("\nPosOrden");
a.posOrden();
}
}
No hay comentarios.:
Publicar un comentario