Arboles Igual que la lista, el árbol es una estructura de datos. Son muy eficientes para la búsqueda de información. Los árboles soportan estructuras no lineales.
Algunos conceptos de la estructura de datos tipo árbol:
Nodo hoja: Es un nodo sin descendientes (Nodo terminal)
Ej. Nodos E ? F ? C y D.
Nodo interior: Es un nodo que no es hoja.
Ej. Nodos A y B.
Nivel de un árbol: El nodo A está en el nivel 1 sus descendientes directos están en el nivel 2 y así sucesivamente.
El nivel del árbol está dado por el nodo de máximo nivel.
Ej. Este árbol es de nivel 3.
Grado de un nodo: es el número de nodos hijos que tiene dicho nodo (solo se tiene en cuenta los nodos interiores)
Ej. El nodo A tiene grado 3.
El nodo B tiene grado 2.
Los otros nodos no tienen grado porque no tienen descendientes.
Grado de un árbol: Es el máximo de los grados de todos los nodos de un árbol.
Ej. El grado del árbol es 3.
Longitud de camino del nodo x: Al número de arcos que deben ser recorridos para llegar a un nodo x, partiendo de la raiz.
La raiz tiene longitud de camino 1, sus descendientes directos tienen longitud de camino 2, etc. En forma general un nodo en el nivel i tiene longitud de camino i.
Árbol binario: Un árbol es binario si cada nodo tiene como máximo 2 descendientes.
1) NODO DE UN ARBOL:
public class Nodo {
int dato;
Nodo Hizq, Hder;
//Constructores
Nodo(int Elem) {
dato = Elem;
Nodo Hizq, Hder = null;
}
//Insercion de un elemento
public void InsertaNodo(int Elem) {
if (Elem < dato) {
if (Hizq == null) {
Hizq = new Nodo(Elem);
} else {
Hizq.InsertaNodo(Elem);
}
} else {
if (Elem > dato) {
if (Hder == null) {
Hder = new Nodo(Elem);
} else {
Hder.InsertaNodo(Elem);
}
}
}
}
}
2) ClASE COLA :
public class Cola {
NodosListaA PrimerNodo;
NodosListaA UltimoNodo;
String Nombre;
//Constructor construye una lista vacia con un nombre de List
public Cola() {
this("Lista");
}
//Constructor
public Cola(String s) {
Nombre = s;
PrimerNodo = UltimoNodo = null;
}
//Retorna True si Lista Vacía
public boolean VaciaLista() {
return PrimerNodo == null;
}
//Inserta un Elemento al Frente de la Lista
public void InsertaInicio(Nodo ElemInser) {
if (VaciaLista()) {
PrimerNodo = UltimoNodo = new NodosListaA(ElemInser);
} else {
PrimerNodo = new NodosListaA(ElemInser, PrimerNodo);
}
}
//Inserta al Final de la Lista
public void InsertaFinal(Nodo ElemInser) {
if (VaciaLista()) {
PrimerNodo = UltimoNodo = new NodosListaA(ElemInser);
} else {
UltimoNodo = UltimoNodo.siguiente = new NodosListaA(ElemInser);
}
}
//Eliminar al Inicio
public void EliminaInicio() {
if (VaciaLista()) {
System.out.println("No hay elementos");
}
// Restablecer las referencias de PrimerNodo y UltimoNodo
if (PrimerNodo.equals(UltimoNodo)) {
PrimerNodo = UltimoNodo = null;
} else {
PrimerNodo = PrimerNodo.siguiente;
}
}
//Elimina al final
public void EliminaFinal() {
if (VaciaLista()) {
System.out.println("No hay elementos");
}
// Restablecer las referencias de PrimerNodo y UltimoNodo
if (PrimerNodo.equals(UltimoNodo)) {
PrimerNodo = UltimoNodo = null;
} else {
NodosListaA Actual = PrimerNodo;
while (Actual.siguiente != UltimoNodo) {
Actual = Actual.siguiente;
}
UltimoNodo = Actual;
Actual.siguiente = null;
}
}
}
3) CLASE NODOLISTA: */
public class NodosListaA {
Nodo datos;
NodosListaA siguiente;
//Construtor Crea un nodo del tipo Object
NodosListaA(Nodo valor) {
datos = valor;
siguiente = null; //siguiente con valor de nulo
}
// Constructor Crea un nodo del Tipo Object y al siguiente nodo de la lista
NodosListaA(Nodo valor, NodosListaA signodo) {
datos = valor;
siguiente = signodo; //siguiente se refiere al siguiente nodo
}
}
5) CLASE ARBOL :
public class Arbol {
Cola Cola = new Cola();
Nodo Padre;
Nodo Raiz;
//Constructor
public Arbol() {
Raiz = null;
}
//Insercion de un elemento en el arbol
public void InsertaNodo(int Elem) {
if (Raiz == null) {
Raiz = new Nodo(Elem);
} else {
Raiz.InsertaNodo(Elem);
}
}
//Preorden Recursivo del arbol
public void Preorden(Nodo Nodo) {
if (Nodo == null) {
return;
} else {
System.out.print(Nodo.dato + " ");
Preorden(Nodo.Hizq);
Preorden(Nodo.Hder);
}
}
//PostOrden recursivo del arbol
public void PostOrden(Nodo Nodo) {
if (Nodo == null) {
return;
} else {
PostOrden(Nodo.Hizq);
PostOrden(Nodo.Hder);
System.out.print(Nodo.dato + " ");
}
}
//Inorden Recursivo del arbol
public void Inorden(Nodo Nodo) {
if (Nodo == null) {
return;
} else {
Inorden(Nodo.Hizq);
System.out.print(Nodo.dato + " ");
Inorden(Nodo.Hder);
}
}
//Busca un elemento en el arbol
void Busqueda(int Elem, Nodo A) {
if ((A == null) | (A.dato == Elem)) {
System.out.print(A.dato + " ");
return;
} else {
if (Elem > A.dato) {
Busqueda(Elem, A.Hder);
} else {
Busqueda(Elem, A.Hizq);
}
}
}
//Altura del arbol
public int Altura(Nodo Nodo) {
int Altder = (Nodo.Hder == null ? 0 : 1 + Altura(Nodo.Hder));
int Altizq = (Nodo.Hizq == null ? 0 : 1 + Altura(Nodo.Hizq));
return Math.max(Altder, Altizq);
}
//Recorrido en anchura del arbol
public void Anchura(Nodo Nodo) {
Cola cola = new Cola();
Nodo T = null;
System.out.print("El recorrido en Anchura es: ");
if (Nodo != null) {
cola.InsertaFinal(Nodo);
while (!(cola.VaciaLista())) {
T = cola.PrimerNodo.datos;
cola.EliminaInicio();
System.out.print(T.dato + " ");
if (T.Hizq != null) {
cola.InsertaFinal(T.Hizq);
}
if (T.Hder != null) {
cola.InsertaFinal(T.Hder);
}
}
}
System.out.println();
}
}
6) CLASE PRINCIPAL:
public class ArbolesDaniel {
public static void main(String[] args) {
Arbol A = new Arbol();
A.InsertaNodo(10);
A.InsertaNodo(7);
A.InsertaNodo(8);
A.InsertaNodo(6);
A.InsertaNodo(12);
A.InsertaNodo(11);
A.InsertaNodo(5);
A.InsertaNodo(4);
A.InsertaNodo(3);
A.InsertaNodo(2);
System.out.print("El recorrido en Preorden es: ");
A.Preorden(A.Raiz);
System.out.println();
System.out.print("El recorrido en Inorden es: ");
A.Inorden(A.Raiz);
System.out.println();
System.out.print("El recorrido en Postorden es: ");
A.PostOrden(A.Raiz);
System.out.println();
System.out.println("La altura del arbol es: " + A.Altura(A.Raiz));
A.Anchura(A.Raiz);
}
}
