Árboles (informatica)

3

Estructura de Datos II Lauro Antonio Arcos Mendez

INTRODUCCIÓN

En esta ultima unidad veremos los temas de árbol, arboles binarios y grafos.

Nos dice que un árbol es una estructura de datos ampliamente usada que imita la forma de un árbol (un conjunto de nodos conectados). Existen dos recorridos típicos para listar los nodos de un árbol: primero en profundidad y primero en anchura. Otros recorridos típicos del árbol son preorden, postorden e inorden. Otro tema que veremos es el de los arboles binarios.

Sus operaciones básicas de un árbol son: enumerar, buscar, si hay un nodo listarlos, borrar un elemente, eliminar un subárbol, añadir un subárbol y encontrar la raíz de cualquier nodo.

Otro tema a estudiar muy importante que analizaremos es lo que son los grafos, su representación grafica y en memoria, sus operaciones que se pueden hacer en ella.

http://es.wikipedia.org/wiki/Estructura_de_datos

4


DEFINICIÓN DE ARBOL

Un árbol es una estructura de datos ampliamente usada que emula la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o mas nodos hijos conectados a él. Se dice que un nodo a es padre de un nodo b, si existe un enlace desde a hasta b (en ese caso, también decimos que b es hijo de a). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja. El árbol También se define como una estructura de datos no lineal. Esta estructura se usa principalmente para representar datos con una relación jerárquica entre sus elementos, como por ejemplo registros, árboles genealógicos y tablas de contenidos. Entre otros tenemos un tipo especial de de árbol que es, llamado árbol binario, que puede ser implementado fácilmente en la computadora.

ARBOLES BINARIOS

Un Árbol Binario es un conjunto de finito de Elementos, de nombre Nodos de forma que:

El Árbol Binario es Vació si no tiene ningún elemento en el. El Árbol Binario contiene un Nodo Raíz y los dos que parten de él, llamados

Nodo Izquierdo y Nodo Derecho.

REPRESENTACIÓN GRÁFICA

La representación gráfica de un árbol binario es la siguiente:

REPRESENTACION DE MEMORIA

Hay dos formas tradicionales de representar un árbol binario en memoria:

Por medio de datos tipo punteros también conocidos como variables dinámicas o listas.

Por medio de arreglos.

5


Sin embargo la más utilizada es la primera, puesto que es la más natural para tratar este tipo de estructuras.

Los nodos del árbol binario serán representados como registros que contendrán como mínimo tres campos. En un campo se almacenará la información del nodo. Los dos restantes se utilizarán para apuntar al subárbol izquierdo y derecho del subárbol en cuestión.

Cada nodo se representa gráficamente de la siguiente manera:

RECORRIDOS

Los Árboles tienen 3 Recorridos Diferentes los cuales son:

Pre-Orden In-Orden Post-Orden

Pre-Orden

Definición:

El Recorrido “Pre-Orden” lo recorre de la siguiente manera, viaje a través del Árbol Binario desplegando el Contenido en la Raíz, después viaje a través del Nodo Izquierdo y después a través del Nodo Derecho.

Detalles:

Temp toma el Valor de la Raíz y compara si el Árbol tiene algún Elemento, de otra manera Desplegara “Árbol Vació…” y terminara el método. Si el Árbol tiene elementos dentro de él, lo recorrerá y viajara a través de los Arreglos Izq y Der para determinar qué valor meter en la Pila y en Temp para de esta manera imprimir el siguiente Elemento correspondiente.

Algoritmo:

6


PreOrd(Arbol, Der, Izq, Pila, Raiz)Temp → RaizTop →Pila[Top] → NuloSi Raiz = NuloImprimir “Árbol Vació…” y SalirRepetir mientras Temp ≠ NuloImprimir Arbol[Temp]Si Der[Temp] ≠ NuloTop → Top + 1Pila[Top] → Der[Temp]Si Izq[Temp] ≠ NuloTemp → Izq[Temp]Si no:Temp → Pila[Top];Top → Top - 1Fin del cicloSalir

Diagrama:

Corrida:

http://www.programacionfacil.com/_detail/estructura_de_datos/image593.jpg?id=estructura_de_datos:arbol_binario

7


In-Orden

Definición:

El Recorrido “In-Orden” lo recorre de la siguiente manera, viaje a través del Árbol Binario desplegando el Contenido en el Nodo Izquierdo después la Raíz y finalmente viaja a través del Nodo Derecho.

Detalles:


Algoritmo:

PreOrd(Arbol, Der, Izq, Pila, Raiz)Temp → RaizTop →Pila[Top] → NuloSi Raiz = NuloImprmir “Arbol Vacio…” y SalirEtiqueta:Mientras Temp ≠ NuloTop → Top + 1Pila[Top] → TempTemp → Izq[Temp]Fin del cicloTemp → Pila[Top]Top → Top - 1


8


Mientras Temp ≠ NuloImprimir Arbol[Temp]Si Der[Temp] ≠ NuloTemp → Der[Temp]Ir a EtiquetaTemp → Pila[Top]Top → Top - 1Fin del cicloSalir

Diagrama:

Corrida:

In-Orden



9


Definición:

El Recorrido “In-Orden” lo recorre de la siguiente manera, viaje a través del Árbol Binario desplegando el Contenido en el Nodo Izquierdo después el Nodo Derecho y finalmente viaja a través de la Raiz.

Detalles:


Algoritmo:

PostOrd(Arbol, Der, Izq, Pila, Raiz)Temp → RaizTop →Pila[Top] → NuloSi Raiz = NuloImprimir “Arbol Vacio…” y SalirEtiqueta:Mientras Temp ≠ NuloTop → Top + 1Pila[Top] → TempSi Der[Temp] ≠ NuloTop → Top + 1Pila[Top] → - (Der[Temp])Temp → Izq[Temp]Temp → Pila[Top]Top → Top - 1Fin del cicloMientras Temp ≥ 0Imprimir Arbol[Temp]Si Arbol[Temp] = Info[Raiz]SalirTemp → Pila[Top]Top → Top - 1Fin del cicloSi Temp < 0Temp = -(Temp)Ir a EtiquetaSalirDiagrama:

10


Corrida:

Búsqueda

Definición:

La Búsqueda es Similar a todas los Métodos anteriores de Búsqueda, simplemente efectúa un recorrido comparando el Elemento que deseas encontrar contra cada uno de los Elementos en los Arreglos.

Detalles:



11


El Algoritmo de Búsqueda compara el Elemento a buscar con cada uno de los datos de nuestro Árbol, compara si el Elemento con el Nodo Raíz, si no se encuentra en la Raíz… compara Elemento contra la Raíz para empezar a viajar por el Árbol respectivamente, usa un método similar al anterior hasta encontrar el Elemento. De otra forma la búsqueda es fallida.

Algoritmo:

Busqueda(Arbol, Der, Izq, Pila, Raiz, Elem)Si Raiz = NuloImprimir “Arbol Vacio”Pos → NuloPad → NuloRegresar Pos y PadSalirSi Elem = Arbol[Raiz]Imprimir “Elemento Encontrado”Pos → RaizPad → NuloRegresar Pos y PadSalirSi Elem < Arbol[Raiz]Temp → Izq[Raiz]Temp2 → RaizSi no:Temp → Der[Raiz]Temp2 → RaizMientras Temp ≠ NuloSi Elem = Arbol[Temp]Imprimir “Elemento Encontrado…”Pos → TempPad → Temp2Regresar Pos y PadSalirSi Elem < Arbol[Temp]Temp2 → TempTemp → Izq[Temp]Si no:Temp2 → TempTemp → Der[Temp]Fin del cicloImprimir “Elemento no Encontrado…”Pos → NuloPad → Temp2Regresar Pos y PadSalir

12


Diagrama:

Corrida:

OPERACIONES DE ÁRBOLES



13


Las operaciones comunes en árboles son:

• Enumerar todos los elementos.

• Buscar un elemento.

• Dado un nodo, listar los hijos (si los hay).

• Borrar un elemento.

• Eliminar un subárbol (algunas veces llamada podar).

• Añadir un subárbol (algunas veces llamada injertar).

• Encontrar la raíz de cualquier nodo.

DEFINICIÓN DE GRAFO

14


Un grafo, G, es un par ordenado de V y A, donde V es el conjunto de vértices o nodos del grafo y A es un conjunto de pares de vértices, a estos también se les llama arcos o ejes del grafo. Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente a dos vértices.

Los grafos representan conjuntos de objetos que no tienen restricción de relación entre ellos. Un grafo puede representar varias cosas de la realidad cotidiana, tales como mapas de carreteras, vías férreas, circuitos eléctricos, etc.

La notación G = A (V, A) se utiliza comúnmente para identificar un grafo.

Los grafos son estructuras de datos no lineales que tienen una naturaleza generalmente dinámica. Su estudio podría dividirse en dos grandes bloques:

Grafos Dirigidos. Grafos no Dirigidos (pueden ser considerados un caso particular de los

anteriores).

Los grafos se constituyen principalmente de dos partes: las aristas, vértices y los caminos que pueda contener el mismo grafo.

Aristas

Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos.

Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une.

Si {a ,b} es una arista, a los vértices a y b se les llama sus extremos.

Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice.

Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo.

Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.

15


Cruce: Son dos aristas que cruzan en un punto.

Vértices

Son los puntos o nodos con los que está conformado un grafo.

Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado.

Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.

Vértice Aislado: Es un vértice de grado cero.

Vértice Terminal: Es un vértice de grado 1.

Caminos

Sean x, y " V, se dice que hay un camino en G de x a y si existe una sucesión finita no vacía de aristas {x,v1}, {v1,v2},..., {vn,y}. En este caso

x e y se llaman los extremos del camino

El número de aristas del camino se llama la longitud del camino.

Si los vértices no se repiten el camino se dice propio o simple.

Si hay un camino no simple entre 2 vértices, también habrá un camino simple entre ellos.

Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino cerrado.

Llamaremos ciclo a un circuito simple

Un vértice a se dice accesible desde el vértice b si existe un camino entre ellos. Todo vértice es accesible respecto a si mismo

REPRESENTACIÓN DE GRAFOS EN PROGRAMAS

16


Hay tres maneras de representar un grafo en un programa: mediante matrices, mediante listas y mediante matrices dispersas.

Representación mediante matrices: La forma más fácil de guardar la información de los nodos es mediante la utilización de un vector que indexe los nodos, de manera que los arcos entre los nodos se pueden ver cómo relaciones entre los índices. Esta relación entre índices se puede guardar en una matriz, que llamaremos de adyacencia.

Representación mediante listas: En las listas de adyacencia lo que haremos será guardar por cada nodo, además de la información que pueda contener el propio nodo, una lista dinámica con los nodos a los que se puede acceder desde él. La información de los nodos se puede guardar en un vector, al igual que antes, o en otra lista dinámica.

Representación mediante matrices dispersas: Para evitar uno de los problemas que teníamos con las listas de adyacencia, que era la dificultad de obtener las relaciones inversas, podemos utilizar las matrices dispersas, que contienen tanta información como las matrices de adyacencia, pero, en principio, no ocupan tanta memoria como las matrices, ya que al igual que en las listas de adyacencia, sólo representaremos aquellos enlaces que existen en el grafo.

RECORRIDO DE UN GRAFO

Recorrer un grafo significa tratar de alcanzar todos los nodos que estén relacionados con uno que llamaremos nodo de salida. Existen básicamente dos técnicas para recorrer un grafo: el recorrido en anchura; y el recorrido en profundidad.

Recorrido en anchura: El recorrido en anchura supone recorrer el grafo, a partir de un nodo dado, en niveles, es decir, primero los que están a una distancia de un arco del nodo de salida, después los que están a dos arcos de distancia, y así sucesivamente hasta alcanzar todos los nodos a los que se pudiese llegar desde el nodo salida.

Recorrido en profundidad: el recorrido en profundidad trata de buscar los caminos que parten desde el nodo de salida hasta que ya no es posible avanzar más. Cuando ya no puede avanzarse más sobre el camino elegido, se vuelve atrás en busca de caminos alternativos, que no se estudiaron previamente.

OPERACIONES BÁSICAS DE LOS GRAFOS

17


En los grafos, como en todas las estructuras de datos, las dos operaciones básicas son insertar y borrar. En este caso, cada una de ellas se desdobla en dos, para insertar/eliminar vértices e insertar/eliminar aristas.

Insertar vértice

La operación de inserción de un nuevo vértice es una operación muy sencilla, únicamente consiste en añadir una nueva entrada en la tabla de vértices (estructura de datos que almacena los vértices) para el nuevo nodo. A partir de ese momento el grafo tendrá un vértice más, inicialmente aislado, ya que ninguna arista llegará a él.

Insertar arista

Esta operación es también muy sencilla. Cuando se inserte una nueva arista en el grafo, habrá que añadir un nuevo nodo a la lista de adyacencia (lista que almacena los nodos a los que un vértice puede acceder mediante una arista) del nodo origen, así si se añade la arista (A,C), se deberá incluir en la lista de adyacencia de A el vértice C como nuevo destino.

Eliminar vértice

Esta operación es inversa a la inserción de vértice. En este caso el procedimiento a realizar es la eliminación de la tabla de vértices del vértice en sí. A continuación habrá que eliminar las aristas que tuviesen al vértice borrado como origen o destino.

Eliminar arista

Mediante esta operación se borra un arco del grafo. Para llevar a cabo esta acción es necesario eliminar de la lista de adyacencia del nodo origen el nodo correspondiente al nodo destino.

Otras operaciones

Las operaciones adicionales que puede incluir un grafo son muy variadas. Además de las clásicas de búsqueda de un elemento o recorrido del grafo, también podemos encontrarnos con ejecución de algoritmos que busquen caminos más cortos entre dos vértices, o recorridos del grafo que ejecuten alguna operación sobre todos los vértices visitados, por citar algunas operaciones de las más usuales.

Arboles.java

18


//Lauro Antonio Arcos Mendezpublic class Arboles {public Arboles() {System.out.println("Un árbol genérico");}

public Arboles(String tipo) {System.out.println("Un árbol tipo " + tipo);}

public Arboles(int altura) {System.out.println("Un árbol de " + altura + " metros");}

public Arboles(int altura,String tipo) {System.out.println("Un " + tipo + " de " + altura + " metros");}

public static void main(String args[]) {Arboles arbol1 = new Arboles(4);Arboles arbol2 = new Arboles("Roble");Arboles arbol3 = new Arboles();Arboles arbol4 = new Arboles(5,"Pino");}}

ArbolBinario.java

19


//Lauro Antonio Arcos Mendez//Definicion de la clase NodoBinarioPublic class ArbolBinario{

int dato;NodoBinario Hizq, Hder;//ConstructoresNodoBinario (int Elem){

dato = Elem;NodoBinario Hizq, Hder = null;

}

//Insercion de un elementopublic void InsertaBinario (int Elem){

if(Elem < dato){if (Hizq == null)

Hizq = new NodoBinario(Elem);else

Hizq.InsertaBinario(Elem);}else{

if (Elem > dato){if (Hder == null)

Hder = new NodoBinario (Elem);else

Hder.InsertaBinario(Elem);}

}}

}

//Definicion de la clase Arbolclass Arbol{

Cola Cola = new Cola();NodoBinario Padre;NodoBinario Raiz;

//Constructorpublic Arbol(){

Raiz = null;}

//Insercion de un elemento en el arbolpublic void InsertaNodo(int Elem){

if(Raiz == null)Raiz = new NodoBinario (Elem);

elseRaiz.InsertaBinario (Elem);

}

20


//Preorden Recursivo del arbolpublic void Preorden (NodoBinario Nodo){

if(Nodo == null)return;

else{System.out.print (Nodo.dato + " ");Preorden (Nodo.Hizq);Preorden (Nodo.Hder);

}}

//PostOrden recursivo del arbolpublic void PostOrden (NodoBinario Nodo){


else{PostOrden (Nodo.Hizq);PostOrden (Nodo.Hder);System.out.print (Nodo.dato + " ");

}}

//Inorden Recursivo del arbolpublic void Inorden (NodoBinario Nodo){


else{Inorden (Nodo.Hizq);System.out.print(Nodo.dato + " ");Inorden (Nodo.Hder);

}}

//Busca un elemento en el arbolvoid Busqueda (int Elem, NodoBinario A){

if((A == null) | (A.dato == Elem)){System.out.print(A.dato + " ");return;

}else{

if(Elem>A.dato)Busqueda (Elem, A.Hder);

elseBusqueda ( Elem, A.Hizq);

}}

21


//Altura del arbolpublic int Altura (NodoBinario 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 arbolpublic void Anchura (NodoBinario Nodo){

Cola cola= new Cola();NodoBinario 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();

}}

//Definición de la Clase NodoListaclass NodosListaA{ NodoBinario datos; NodosListaA siguiente;

//Construtor Crea un nodo del tipo ObjectNodosListaA (NodoBinario valor){

datos =valor; siguiente = null; //siguiente con valor de nulo }

// Constructor Crea un nodo del Tipo Object y al siguiente nodo de la listaNodosListaA (NodoBinario valor, NodosListaA signodo){

datos = valor; siguiente = signodo; //siguiente se refiere al siguiente nodo

}}

//Definición de la Clase Listaclass Cola{

22


NodosListaA PrimerNodo;NodosListaA UltimoNodo;String Nombre;

//Constructor construye una lista vacia con un nombre de Listpublic Cola(){

this ("Lista");}

//Constructor public Cola (String s){

Nombre = s; PrimerNodo = UltimoNodo =null;}

//Retorna True si Lista Vacíapublic boolean VaciaLista() {

return PrimerNodo == null;}

//Inserta un Elemento al Frente de la Listapublic void InsertaInicio (NodoBinario ElemInser){

if(VaciaLista()) PrimerNodo = UltimoNodo = new NodosListaA (ElemInser); else PrimerNodo = new NodosListaA (ElemInser, PrimerNodo);}

//Inserta al Final de la Listapublic void InsertaFinal(NodoBinario ElemInser){

if(VaciaLista()) PrimerNodo = UltimoNodo = new NodosListaA (ElemInser); else UltimoNodo=UltimoNodo.siguiente =new NodosListaA (ElemInser);}

//Eliminar al Iniciopublic 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;}

23


//Elimina al finalpublic void EliminaFinal (){ if(VaciaLista()) System.out.println ("No hay elementos");

// Restablecer las referencias de PrimerNodo y UltimoNodoif (PrimerNodo.equals (UltimoNodo))

PrimerNodo = UltimoNodo = null; else{ NodosListaA Actual =PrimerNodo;

while (Actual.siguiente != UltimoNodo)Actual = Actual.siguiente;

UltimoNodo =Actual;Actual.siguiente = null;

}}

}

class ArbolBinarioA{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);

}}

24


CONCLUSIÓN

Como ya vimos en esta unidad los arboles son estructura de datos que son como los arboles y me refiero a su forma y estructura que vemos donde quiera que vamos porque un árbol tiene ramas y mas ramas y todo viene de una raíz, tienen un conjunto de nodos conectados, digamos que estos nodos fueran sus ramas que hacen que estén conectados.

El árbol binario con tiene un nodo raíz y los dos que parten de él se le llaman nodo izquierdo y nodo derecho.

Los arboles son muy importantes porque pueden ser utilizados por ejemplo como ayuda para realizar búsquedas en conjuntos de datos.

Por otro lado los grafos que se puede decir que significa trazar nos son de utilidad para representar gráficamente un problema dibujando un grafo como un conjunto de puntos y con líneas conectándolos.

BIBLIOGRAFÍA

http://www.mitecnologico.com/Main/ArbolesDefinicion.html

http://www.mitecnologico.com/Main/ArbolesDefinicion.html

25


http://www.mitecnologico.com/Main/ OperacionesBasicasArbolesBinarios

http://www.programacionfacil.com/estructura_de_datos/ arbol_binario

http://es.wikipedia.org/wiki/Grafo_%28estructura_de_datos%29

http://www.mitecnologico.com/Main/RecorridosEnUnArbol

http://apuntes.rincondelvago.com/grafos.html

http://apuntes.rincondelvago.com/grafos.html

http://www.mitecnologico.com/Main/RecorridosEnUnArbol

http://es.wikipedia.org/wiki/Grafo_(estructura_de_datos)

http://www.programacionfacil.com/estructura_de_datos/arbol_binario

http://www.programacionfacil.com/estructura_de_datos/arbol_binario

http://www.mitecnologico.com/Main/OperacionesBasicasArbolesBinarios

http://www.mitecnologico.com/Main/OperacionesBasicasArbolesBinarios

Árboles (informatica)

Documents

Transcript of Árboles (informatica)