ARBOL
MARTIN ELIAS ALVAREZ CONTRERAS
DANIELA ZUÑIGA MONTES.
JIMMY JOSE SANCHEZ GARCIA
Ingeniero de sistema.
UNIVERSIDAD DE CÓRDOBA
FACULTAD DE INGENIERÍA
DEPARTAMENTO DE INGENIERÍA INDUSTRIAL
PROGRAMACION II
MONTERÍA
2019
QUÉ ES UN ÁRBOL
Los Árboles son las estructuras de datos más utilizadas, pero también
una de las más complejas, Los Árboles se caracterizan por almacenar
sus nodos en forma jerárquica y no en forma lineal como las Listas
Ligadas, Colas, Pilas, etc.
Un árbol consiste en un conjunto de nodos o vértices y un conjunto
de aristas o arcos que satisface unos requisitos
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.
o Esta estructura se caracteriza por que cada nodo solo
puede tener máximo 2 hijo, dicho de otra manera, es un
Árbol n-ario de Grado 2.
Árbol n-ario: los arboles n-arios son aquellos arboles donde el
número máximo de hijos por nodo es de N, en la figura 7
podemos apreciar dos árboles con grado 2 y grado 3, estos dos
árboles también los podemos definir como Árbol n-ario con n = 2
y n=3 respectivamente.
Á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
package pruebaarbol;
import [Link];
/**
*
* @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
[Link](new Nodo(6));
//Se asigna el valor 5 al nodo que sera hijo del nodo 3 a la izquierda
[Link](new Nodo(5));
//Se asigna el valor 4 al nodo que sera hijo del nodo 4 a la izquierda
[Link](new Nodo(4));
//Se crean el Nodo 2 a la izquierda y el Nodo 3 a la derecha de la raiz
[Link](nodo2);
[Link](nodo3);
//Resultado en pantalla
[Link]("Recorrido Preorden: ");
preOrden(raiz);
[Link]("Recorrido Inorden: ");
inorden(raiz);
[Link]("Recorrido PostOrden: ");
posOrden(raiz);
}
//Metodo Preorden
private static void preOrden(Nodo raiz) {
if (raiz != null) {
[Link]([Link]() + " - ");
preOrden([Link]());
preOrden([Link]());
}
}
//Metodo Inorden
private static void inorden(Nodo raiz) {
if (raiz != null) {
inorden([Link]());
[Link]([Link]()+ " - ");
inorden([Link]());
}
}
//Metodo PostOrden
private static void posOrden(Nodo raiz) {
if (raiz != null) {
posOrden([Link]());
posOrden([Link]());
[Link]([Link]() + " - ");
}
}
}
NODO
package [Link];
/**
*
*
*/
public class Nodo {
//Variables
private int dato;
private Nodo izq;
private Nodo der;
//Constructor
public Nodo(int dato){
[Link] = 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;
}
}
