Download ESTRUCTURA DE DATO ARBOL Las estructuras

Ingeniero Eduardo Robayo Castro
ESTRUCTURAS DE DATOS
SUB-TEMA: ESTRUCTURA DE DATO ARBOL
Las estructuras de datos ARBOL, son muy útiles para búsqueda de información, ya que soportan
organización no lineal como lo hemos visto como las listas.
Para analizar la estructura ARBOL, es necesario entender los siguientes conceptos:
NODO HOJA:
Es un nodo que no tiene descendientes, por ejemplo E, F, C, D.
NODO INTERIOR:
Es un nodo que no es hoja, por ejemplo A y B.
NIVEL DE UN
El nivel del árbol está dado por el nivel de la máxima rama encontrada en
ARBOL:
el árbol, por ejemplo en el árbol de éste ejemplo, el nodo A está en el
nivel 1, los nodos B, C, y D están en el nivel 2, y los nodos E y F están en el
nivel 3. En resumen, éste árbol es de nivel 3.
GRADO DE UN
Es el número de nodos “hijo” que tiene el nodo. Solo aplica para nodos
NODO:
interiores. Por ejemplo, el nodo A tiene grado 3 y el nodo B tiene grado 2.
GRADO DE UN
Es el máximo de los grados de todos los nodos de un árbol. Por ejemplo, el
ARBOL:
árbol de éste ejemplo tiene grado 3.
LONGITUD DE
Es el número de pasos que se deben recorrer para llegar a un nodo,
CAMINO DE NODO: partiendo desde la raíz. La raíz tiene longitud de camino 1. Los nodos del
nivel 2 tienen longitud de camino 2.
ARBOL BINARIO:
Es un árbol en el cual cada nodo tiene como máximo 2 descendientes.
ARBOL BINARIO
El subárbol izquierdo del nodo A, está conformado por los nodos B, D, y E.
El subárbol derecho del nodo A, está conformado por los nodos C y F.
Para cada nodo, el número de nodos de los subárboles izquierdo y
Ingeniero Eduardo Robayo Castro
PERFECTAMENTE
EQUILIBRADO
derecho difieren como máximo en un nodo.
El siguiente árbol NO es perfectamente equilibrado, pues el nodo A tiene
3 nodos en el subárbol izquierdo y solo 1 en el subárbol derecho.
ARBOL BINARIO
ORDENADO
Un árbol binario es ordenado cuando los nodos ubicados a la izquierda
son inferiores al nodo raíz que se está analizando, y los nodos ubicados a
la derecha son mayores.
El siguiente es un árbol binario ordenado:
Para el nodo que tiene el 50:
¿Los nodos del subárbol izquierdo son todos menores a 50?
8, 25, 30 Si
¿Los nodos del subárbol derecho son todos mayores a 50?
70 Si.
Para el nodo que tiene el 25:
¿Los nodos del subárbol izquierdo son todos menores a 25?
8 Si
¿Los nodos del subárbol derecho son todos mayores a 25?
30 Si.
INSERTAR NODOS Y RECORRER UN ARBOL BINARIO ORDENADO
Ingeniero Eduardo Robayo Castro
Crear un árbol binario ordenado que contenga los siguientes nodos:
400, 100, 200, 700.
1. Al principio el árbol está vacío, entonces el nodo raíz apunta a null.
2. Insertar el nodo 400.
3. Insertar el nodo 100.
Si el nodo raíz está apuntado a diferente de null, entonces validar si 100 es mayor o menor que el
nodo al cual apunta el nodo raíz.
Como el nodo es menor, y el subárbol izquierdo es null, entonces se inserta allí.
4. Insertar el nodo 200.
Empezar a comparar siempre desde el nodo raíz.
El nodo 200 es menor que el nodo 400, vamos por el subárbol izquierdo.
El nodo 200 es mayor que el nodo 100, vamos por el subárbol derecho.
Como el subárbol derecho está apuntando a null, entonces se inserta en esa posición.
Ingeniero Eduardo Robayo Castro
5. Insertar el nodo 700.
Se empieza a comparar por el nodo raíz.
El nodo 700 es mayor que el nodo 400, entonces vamos por el subárbol derecho.
El subárbol derecho está apuntando a null, entonces se inserta en esa ubicación.
ROCORRER UN ARBOL
Un árbol se puede recorrer de tres formas:
 Pre-orden
 Entre-orden
 Post-orden
Analicemos el comportamiento de cada una de éstas formas de recorrido del árbol, pero en el
código directamente.
public class ArbolBinarioOrdenado {
class Nodo
{
int info;
Nodo izq, der;
}
Nodo raiz;
public ArbolBinarioOrdenado() {
raiz=null;
}
public void insertar (int info)
{
Nodo nuevo;
Ingeniero Eduardo Robayo Castro
nuevo = new Nodo ();
nuevo.info = info;
nuevo.izq = null;
nuevo.der = null;
if (raiz == null)
raiz = nuevo;
else
{
Nodo anterior = null, reco;
reco = raiz;
while (reco != null)
{
anterior = reco;
if (info < reco.info)
reco = reco.izq;
else
reco = reco.der;
}
if (info < anterior.info)
anterior.izq = nuevo;
else
anterior.der = nuevo;
}
}
private void imprimirPre (Nodo reco)
{
if (reco != null)
{
System.out.print(reco.info + " ");
imprimirPre (reco.izq);
imprimirPre (reco.der);
}
}
public void imprimirPre ()
{
imprimirPre (raiz);
System.out.println();
}
Ingeniero Eduardo Robayo Castro
private void imprimirEntre (Nodo reco)
{
if (reco != null)
{
imprimirEntre (reco.izq);
System.out.print(reco.info + " ");
imprimirEntre (reco.der);
}
}
public void imprimirEntre ()
{
imprimirEntre (raiz);
System.out.println();
}
private void imprimirPost (Nodo reco)
{
if (reco != null)
{
imprimirPost (reco.izq);
imprimirPost (reco.der);
System.out.print(reco.info + " ");
}
}
public void imprimirPost ()
{
imprimirPost (raiz);
System.out.println();
}
public static void main (String [] ar)
{
ArbolBinarioOrdenado abo = new ArbolBinarioOrdenado ();
abo.insertar (100);
abo.insertar (50);
abo.insertar (25);
abo.insertar (75);
abo.insertar (150);
Ingeniero Eduardo Robayo Castro
System.out.println ("Impresion preorden: ");
abo.imprimirPre ();
System.out.println ("Impresion entreorden: ");
abo.imprimirEntre ();
System.out.println ("Impresion postorden: ");
abo.imprimirPost ();
}
}
La salida de ésta aplicación es la siguiente: