Estructuras de datos y algoritmos
Oscar Bedoya.
[email protected]
http://eisc.univalle.edu.co/~oscarbed/Estructuras/
Edificio 331, 2º piso, E.I.S.C.
Árboles
Caso de implementación:
Árboles de búsqueda binaria
Arboles
NodoArbol
izquierdo
dato
derecho
Arboles
NodoArbol
25
20
30
23
39
Arboles
NodoArbol
raíz
25
20
30
23
39
Arboles
NodoArbol
raíz
22
25
20
30
23
39
Arboles
NodoArbol
raíz
32
25
20
30
23
39
Árboles
public class NodoArbol{
NodoArbol izquierdo;
int dato;
NodoArbol derecho;
public NodoArbol (int d)
{
dato = d;
izquierdo = derecho = null;
}
Arboles
NodoArbol
d
dato
Arboles
NodoArbol
d
dato
Si d es menor que dato, e izquierdo es null, al campo izquierdo
le asigno el nodo a insertar
Arboles
NodoArbol
dato
d
Si d es menor que dato, e izquierdo es null, al campo izquierdo
le asigno el nodo a insertar
Arboles
NodoArbol
d
dato
dato1
Arboles
NodoArbol
d
dato
dato1
Si d es menor que dato, e izquierdo es diferente de null, el
problema se reduce ahora a insertar el nodo con el dato d, en
el nodo con dato1
Arboles
NodoArbol
d
dato1
Si d es menor que dato, e izquierdo es diferente de null, el
problema se reduce ahora a insertar el nodo con el dato d, en
el nodo con dato1
Arboles
NodoArbol
d
dato
Arboles
NodoArbol
d
dato
Si d es mayor que dato, y derecha es null, al campo derecha le
asigno el nodo a insertar
Arboles
NodoArbol
dato
d
Si d es mayor que dato, y derecha es null, al campo derecha le
asigno el nodo a insertar
Arboles
NodoArbol
d
dato
dato1
Arboles
NodoArbol
d
dato
dato1
Si d es mayor que dato, y derecho es diferente de null, el
problema se reduce ahora a insertar el nodo con el dato d, en
el nodo con dato1
Arboles
NodoArbol
d
dato1
Si d es mayor que dato, y derecho es diferente de null, el
problema se reduce ahora a insertar el nodo con el dato d, en
el nodo con dato1
Árboles
public void insertar (int d)
{
if (d < dato)
{
if (izquierdo == null)
izquierdo = new NodoArbol(d);
else
izquierdo.insertar(d);
}
else
if (d > dato)
{
if (derecho == null)
derecho = new NodoArbol(d);
else
derecho.insertar(d);
}
}
Arboles
ArbolBinario
raiz
Al crear el árbol binario, se crea
el nodo raiz con valores null
Arboles
Árbol binario (insertar con raíz vacía)
raíz
d
Como la raíz tiene null, a la raíz le asigno el nodo con el nuevo
dato
Arboles
Árbol binario (insertar con raíz vacía)
raíz
d
Como la raíz tiene null, a la raíz le asigno el nodo con el nuevo
dato
Arboles
Árbol binario (insertar con raíz no vacía)
d
raíz
24
Como la raíz tiene un dato, se deben examinar las posibilidades
de insertar el nuevo nodo a la izquierda o a la derecha, esto lo
hace el método insertar implementado para cada nodo
Árboles
public class ArbolBinario{
private NodoArbol raiz;
public ArbolBinario( )
{
raiz = null;
}
Árboles
public void insertarNodo (int d )
{
if( raiz == null)
raiz = new NodoArbol(d);
else
raiz.insertar(d);
}
Árboles
Recorridos del árbol
•Preoden
•Inorden
•Posorden
Arboles
Recorrido Preorden
24
21
Nodo.dato
Preorden(nodo.izquierdo)
Preorden(nodo.derecha)
29
Arboles
Recorrido Preorden
24
Si nodo==null
21
Nodo.dato
Preorden(nodo.izquierdo)
Preorden(nodo.derecha)
return
Árboles
public void preorden (NodoArbol nodo)
{
if (nodo == null)
return;
System.out.print(nodo.dato+" ");
preorden(nodo.izquierdo);
preorden(nodo.derecho);
}
Árboles
public void preordenTraversal ( )
{
preorden(raiz);
}
Descargar

Árboles