capitulo vi Árboles y grafosvirtual.usalesiana.edu.bo/web/conte/archivos/285.pdf · Árboles y...

Programación II Lic. Katya Pérez Martínez Ingenieria de Sistemas Lic. Gladys Chuquimia

79

Capitulo VI Árboles y Grafos

6.1. Definición

6.2. Conceptos Básicos

a. Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo, 'L' y 'M' son hijos de 'F'.

b. Nodo padre: nodo que

contiene un puntero al nodo actual. En el ejemplo, el nodo 'A' es padre de 'B', 'C' y 'D'.

Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos.

Tu vida no cambia cuando cambia tu jefe, Cuando tus amigos cambian, Cuando tus padres cambian, Cuando tu pareja cambia.

Tu vida cambia, cuando tu cambias, Eres el único responsable por ella.

"examínate.. Y no te dejes vencer"


80

Los árboles con los que trabajaremos tienen otra característica importante: cada nodo sólo puede ser apuntado por otro nodo, es decir, cada nodo sólo tendrá un padre. Esto hace que estos árboles estén fuertemente jerarquizados, y es lo que en realidad les da la apariencia de árboles. En cuanto a la posición dentro del árbol:

c. Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos

al árbol. En el ejemplo, ese nodo es el 'A'. d. Nodo hoja: nodo que no tiene hijos. En el ejemplo hay varios: 'G', 'H', 'I', 'K', 'L',

'M', 'N' y 'O'. e. Nodo rama: aunque esta definición apenas la usaremos, estos son los nodos que

no pertenecen a ninguna de las dos categorías anteriores. En el ejemplo: 'B', 'C', 'D', 'E', 'F' y 'J'.

Otra característica que normalmente tendrán nuestros árboles es que todos los nodos contengan el mismo número de punteros, es decir, usaremos la misma estructura para todos los nodos del árbol. Esto hace que la estructura sea más sencilla, y por lo tanto también los programas para trabajar con ellos. Tampoco es necesario que todos los nodos hijos de un nodo concreto existan. Es decir, que pueden usarse todos, algunos o ninguno de los punteros de cada nodo. Un árbol en el que en cada nodo o bien todos o ninguno de los hijos existe, se llama árbol completo. En una cosa, los árboles se parecen al resto de las estructuras que hemos visto: dado un nodo cualquiera de la estructura, podemos considerarlo como una estructura independiente. Es decir, un nodo cualquiera puede ser considerado como la raíz de un árbol completo. Existen otros conceptos que definen las características del árbol, con relación a su tamaño:

f. Orden: es el numero potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc.

g. Grado: el número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del ejemplo, el grado es tres, ya que tanto 'A' como 'D' tienen tres hijos, y no existen elementos con más de tres hijos.


81

h. Nivel: se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero y el de sus hijos uno. Así sucesivamente. En el ejemplo, el nodo 'D' tiene nivel 1, el nodo 'G' tiene nivel 2, y el nodo 'N', nivel 3.

i. Altura: la altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de altura de ramas. El árbol del ejemplo tiene altura 3, la rama 'B' tiene altura 2, la rama 'G' tiene altura 1, la 'H' cero, etc.

Los árboles de orden dos son bastante especiales, de hecho les dedicaremos varios capítulos. Estos árboles se conocen también como árboles binarios. Frecuentemente, aunque tampoco es estrictamente necesario, para hacer más fácil moverse a través del árbol, añadiremos un puntero a cada nodo que apunte al nodo padre. De este modo podremos avanzar en dirección a la raíz, y no sólo hacia las hojas. Es importante conservar siempre el nodo raíz ya que es el nodo a partir del cual se desarrolla el árbol, si perdemos este nodo, perderemos el acceso a todo el árbol. El nodo típico de un árbol difiere de los nodos que hemos visto hasta ahora para listas, aunque sólo en el número de nodos.

6.3. Árboles Binarios. Un arbol binario es un conjunto finito de nodos que puede estar vacío o está compuesto por un nodo raíz y dos subárboles binarios disjuntos llamados subárbol izquierdo y subárbol derecho.. Un subárbol izquierdo o derecho puede esta vacío. Es decir en un árbol binario cada nodo puede tener 0, 1 o 2 nodos hijos.

• Un Árbol Binario es Completo si es Pleno y todas sus hojas tienen exactamente la misma profundidad.

• Un Árbol Binario es Casi-Completo si todos sus niveles están completos,

excepto posiblemente el más profundo, en cuyo caso las hojas ocupan las posiciones de más a la izquierda.

• Propiedades de un AB Completo:

o El número de nodos en el nivel k-ésimo es 2k.


82

o El número total de nodos desde la raíz hasta el nivel k-ésimo es 2k+1-1, o El número total de nodos internos desde la raíz hasta el nivel k-ésimo es

2k-1. • Notación

o izq(v): Hijo (o subárbol) izquierdo de v o der(v): Hijo (o subárbol) derecho de v.

6.4. Representación De Árboles Binarios Estructura estática representada mediante un vector T Al igual que las listas, los árboles también están constituidos por un conjunto de nodos del siguiente modo: La definición en C del nodo es muy parecida a la de listas doblemente encadenadas: El movimiento a través de árboles, salvo que implementemos punteros al nodo padre, será siempre partiendo del nodo raíz hacia un nodo hoja. Cada vez que lleguemos a un nuevo nodo podremos optar por cualquiera de los nodos a los que apunta para avanzar al siguiente nodo. En general, intentaremos que exista algún significado asociado a cada uno de los punteros dentro de cada nodo, los árboles que estamos viendo son abstractos, pero las aplicaciones no tienen por qué serlo. Ejemplo

a. Un ejemplo de estructura en árbol es el sistema de directorios y ficheros de un sistema operativo. Aunque en este caso se trata de árboles con nodos de dos tipos, nodos directorio y nodos fichero, podríamos considerar que los nodos hoja son ficheros y los nodos rama son directorios.

struct nodo { int info; nodo *izq; nodo *der; }; typedef nodo *ARBOL;


83

b. Otro ejemplo podría ser la tabla de contenido de un libro, por ejemplo de este mismo curso, dividido en capítulos, y cada uno de ellos en subcapítulos. Aunque el libro sea algo lineal, como una lista, en el que cada capítulo sigue al anterior, también es posible acceder a cualquier punto de él a través de la tabla de contenido.

c. También se suelen organizar en forma de árbol los organigramas de mando en empresas o en el ejército, y los árboles genealógicos.

6.5. Recorridos El modo evidente de moverse a través de las ramas de un árbol es siguiendo los punteros, del mismo modo en que nos movíamos a través de las listas. Esos recorridos dependen en gran medida del tipo y propósito del árbol, pero hay ciertos recorridos que usaremos frecuentemente. Se trata de aquellos recorridos que incluyen todo el árbol. Hay tres formas de recorrer un árbol completo, y las tres se suelen implementar mediante recursividad. En los tres casos se sigue siempre a partir de cada nodo todas las ramas una por una, estos recorridos son:

PreOrden u “Orden Previo'' IinOrden u “Orden Interno o Simétrico'" PostOrden u “Orden Posterior'"

Los cuales se ejemplifican a continuación Ejemplo: Ejemplo: Un recorrido de un árbol (binario) A es una secuencia o lista de nodos que visita todos los n nodos de A de alguna forma sistemática. Supongamos que tenemos un árbol binario y queremos recorrerlo por completo. Partiremos del nodo raíz:

RecorrerArbol(raiz);

Preorden: <A, B, C> Inorden: <B, A, C> Postorden: <B, C, A>


84

La función RecorrerArbol, aplicando recursividad, será tan sencilla como invocar de nuevo a la función RecorrerArbol para cada una de las ramas: Lo que diferencia los distintos métodos de recorrer el árbol no es el sistema de hacerlo, sino el momento que elegimos para procesar el valor de cada nodo con relación a los recorridos de cada una de las ramas. La implementación de los tres tipos es la siguiente: In-orden: En este tipo de recorrido, el valor del nodo se procesa después de recorrer la primera rama y antes de recorrer la última. Esto tiene más sentido en el caso de árboles binarios,

void InOrden(ARBOL raiz) { if (raiz == NULL) return; InOrden (raiz->izq); cout<<raiz->info; InOrden (raiz->der); }

El siguiente árbol sería recorrido así: 5,15,17,9,3,1,2,19,25,23

1 15 2 5 9 19 17 3 23 25

Si el árbol no esta vació se realizan los siguientes pasos: 1º.- Recorrer en INORDEN el subarbol izquierdo. 2º.- Procesar la Raiz. 3º.- Recorrer en INORDEN el subarbol derecho.

void RecorrerArbol(ARBOL raiz) { if(a == NULL) return; RecorrerArbol(raiz->izq); RecorrerArbol(raiz->der); }


85

Pre-orden: En este tipo de recorrido, el valor del nodo se procesa antes de recorrer las ramas: El árbol sería recorrido así: 1,15,5,9,17,3,2,19,23,25

Si el árbol no esta vacio se realizan los siguientes pasos:

1º.- Procesar Raiz. 2º.- Recorrer en PREORDEN el izquierdo. 3º.- Recorrer en PREORDEN el derecho.

Post-orden: En este tipo de recorrido, el valor del nodo se muestra después de recorrer todas las ramas:

void PostOrden(ARBOL raiz) { if (raiz == NULL) return; PostOrden (raiz->izq); PostOrden (raiz->der); cout<<raiz->info; }

El árbol sería recorrido así: 5,17,3,9,15,25,23,19,2,1 Si el árbol no esta vacio se realizan los siguientes pasos: 1º.- Recorrer en POSTORDEN el izquierdo. 2º.- Recorrer en POSTORDEN el derecho. 3º.- Procesar raiz.

void PreOrden( ARBOL raiz) { if ( raiz == NULL) return; cout<<raiz->info; PreOrden (raiz->izq); PreOrden (raiz->der ); }


86

6.6. Árboles Binarios De Busqueda (Abb) Árbol binario en el cual todos sus nodos cumplen que los nodos de su subárbol izquierdo tienen un valor inferior a él, y los nodos de su subárbol derecho tienen un valor superior a él. No existen valores repetidos.

25 12 37 1 30 63 9 29 48 11 40

6.7. Operaciones Sobre Árboles Binarios De Busqueda De nuevo tenemos casi el mismo repertorio de operaciones de las que disponíamos con las listas:

• Creación de un nuevo nodo • Inserción de nuevos nodos • Búsqueda • Eliminación


87

Creación De Un Nuevo Nodo Inserción De Un Elemento. Hacer un procedimiento que reciba como parámetro el puntero a la raíz de un ABB y el elemento ELEM y lo inserte en su sitio correspondiente.

ARBOL getnodo() { ARBOL p; p=(ARBOL)malloc(sizeof(struct tiponodo)); return p; } ARBOL creaArbol(int dato) { ARBOL p; p=getnodo(); p->info=dato; p->der=NULL; p->izq=NULL; p->padre=NULL; return p; } void inserta(PN raiz, int dato) {int sw=0; PN q; q=getnodo(); q->info=dato; q->izq=NULL; q->der=NULL; q->padre=raiz; while(sw==0) { if(q->info<raiz->info) { if(raiz->izq==NULL) {raiz->izq=q; sw=1; } else raiz=raiz->izq; } if(raiz->izq==NULL) {raiz->der=q; sw=1; } else raiz=raiz->der; } }


88

Busqueda De Un Elemento. Hacer un procedimiento que se llama BUSCAR que reciba como parámetro el puntero raiz de un ABB, un elemento a buscar en la variable ELEM del mismo tipo que los que forman el arbol y una variable POS en la que devolverá la dirección de memoria del nodo que contiene el elemento ELEM, en caso de no encontrarse ese elemento devolverá NULL

Buscar y Eliminar Un Elemento Para eliminar un determinado elemento de un árbol, primero se debe encontrar dicho elemento y luego se debe considerar uno de los siguientes casos:

• Si el nodo buscado es una hoja • Si el nodo buscado tiene un hijo • Si el nodo buscado tiene dos hijos

void insertar (ARBOL raiz, int elem) { if(raiz==NULL) { raiz=new tiponodo(); raiz->info=elem; raiz->izq= NULL; raiz->der= NULL; } else if( raiz->info==elem ) cout<<”repetido”; else if(elem < raiz->info) insertar (raiz->izq, elem); else insertar (raiz->der, elem);

}

void buscar (ARBOL raiz, int elem, int *pos) {int auxpos;

if (raiz==NULL) *pos=NULL; else if(raiz->info==elem) *pos =raiz; else if(elem < raiz->info) buscar ( raiz->izq, elem, &auxpos); else buscar (raiz->der, elem, &auxpos); }


89

Con 2 hijos: se sustituye el elemento a borrar por su anterior en un recorrido en INORDEN, y una vez hecho hay que deshacerse de este último. Dentro del subarbol izquierdo del elemento a suprimir, el que esté más a la derecha es el que ocupa su posición, ya que es su anterior en un recorrido en INORDEN.

void encontar(ARBOL raiz, int elem) { ARBOL p, ant; ant = NULL ; p = raiz ; while (( p-> info != elem ) && ( p<> NULL ) ) { ant = p ; if( elem<p-> info) p= p-> izq ; else p = p-> der ; } if(p != NULL ) { if(p == raiz) suprimir ( raiz ) ; else if(p=ant->izq ) suprimir(ant->izq); else suprimir ( ant -> der ) ; } }

void suprimir ( var p : arbol ) ; { ARBOL temp , ant; if(p->izq == NULL) p = p->der; else if(p -> der == NULL) p = p->izq; else { ant = p; temp = p->izq; while ( temp -> der != NULL ) { ant = temp; temp = temp->der; } p -> info = temp->info ; if(ant==p) ant->izq = temp->izq; else ant->der = temp->izq; } }


90

6.8. Árboles ordenados Un árbol ordenado, en general, es aquel a partir del cual se puede obtener una secuencia ordenada sigui}o uno de los recorridos posibles del árbol: inorden, preorden o postorden. En estos árboles es importante que la secuencia se mantenga ordenada aunque se añadan o se eliminen nodos. Existen varios tipos de árboles ordenados, que veremos a continuación:

• Árboles binarios de búsqueda (ABB): son árboles de orden 2 que mantienen una secuencia ordenada si se recorren en inorden.

• Árboles AVL: son árboles binarios de búsqueda equilibrados, es decir, los niveles de cada rama para cualquier nodo no difieren en más de 1.

• Árboles perfectamente equilibrados: son árboles binarios de búsqueda en los que el número de nodos de cada rama para cualquier nodo no defieren en más de 1. Son por lo tanto árboles AVL también.

• Árboles 2-3: son árboles de orden 3, que contienen dos claves en cada nodo y que están también equilibrados. También generan secuencias ordenadas al recorrerlos en inorden.

• Árboles-B: caso general de árboles 2-3, que para un orden M, contienen M-1 claves.

Salvo que trabajemos con árboles especiales, como los que veremos más adelante, las inserciones serán siempre en punteros de nodos hoja o en punteros libres de nodos rama. Con estas estructuras no es tan fácil generalizar, ya que existen muchas variedades de árboles. •Añadir o insertar elementos. •Buscar o localizar elementos. •Borrar elementos. •Moverse a través del árbol. •Recorrer el árbol completo. Los algoritmos de inserción y borrado dependen en gran medida del tipo de árbol que estemos implementando, de modo que por ahora los pasaremos por alto y nos centraremos más en el modo de recorrer árboles.


91

6.9. Grafos 6.9.1. Definiciones Básicas Un grafo G es un par (V,E) donde V es un conjunto (llamado conjunto de vértices) y E un subconjunto de VxV (conjunto de aristas). Gráficamente representaremos los vértices por puntos y las aristas por líneas que los unen. Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente 2 vértices. Llamaremos orden de un grafo a su número de vértices, |V|. Si |V| es finito se dice que el grafo es finito. En este curso estudiaremos los grafos finitos, centrándonos sobre todo en grafos no dirigidos. También supondremos, a no ser que se diga lo contrario, que entre dos vértices hay, como mucho, una arista y que toda arista une dos vértices distintos.

Aristas Si la arista carece de dirección se denota indistintamente {a,b} o {b,a}, si}o 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.

Vértices Dos vértices v, w se dice que son adyacentes’ si {v,w}∈A (o sea, si existe una arista entre ellos) 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.


92

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. Cu&&o 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

-

Ejemplos De Grafos 1.- Grafo regular: Aquel con el mismo grado en todos los vértices. Si ese grado es k lo llamaremos k-regular. Por ejemplo, el primero de los siguientes grafos es 3-regular, el segundo es 2-regular y el tercero no es regular 2.- Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto Ejemplo.- de los dos grafos siguientes el primero es bipartito y el segundo no lo es


93

3.- Grafo completo: Aquel con una arista entre cada par de vértices. Un grafo completo con n vértices se denota Kn. A continuación pueden verse los dibujos de K3, K4, K5 y K6 Todo grafo completo es regular porque cada vértice tiene grado |V|-1 al estar conectado con todos los otros vértices. Un grafo regular no tiene por qué ser completo. 4.- Un grafo bipartido regular se denota Km,n donde m, n es el grado de cada conjunto disjunto de vértices.


94

A continuación ponemos los dibujos de K1,2, K3,3, y K2,5 Representacion De Grafos


95

EJERCICIOS

1. Hacer un seguimiento del siguiente algoritmo con el árbol que se da. void ejercicio(ARBOL raiz) { if( raiz!=NULL) { if( raiz->info % 2 == 0) cout<<raiz->info; ejercicio(raiz->izq); ejercicio(raiz->der); if(raiz->info>0) cout<<raiz->info; } }

1 2 9 3 8 10 15 11 16 4 5 12 6 13 7 14 ¿Obtendriamos: 2, 4, 4, 6, 7, 6, 5, 3, 8, 8, 2, 10, 12, 14, 14, 13, 12, 11, 10, 16, 16, 15, 9,1?


96

2. Dada la siguiente secuencia de números: 25, 12, 1, 9, 37, 30, 63, 48, 29, 11, 4

construir el ABB que genera dicha secuencia si el orden en el que entran en el árbol es el que se establece.

25 12 37 1 30 63 9 29 48 11 40

3. Dado un árbol binario de busqueda , que contiene el nombre, el apellido y la edad de un grupo de personas , ordenados por edades . Se pide : Hacer un algoritmo que visualice los datos de las personas de mayor a menor edad .

4. Dado un ABB que contiene números enteros .

Se pide : - Hacer un procedimiento que reciba como parámetros: el puntero a raiz del arbol , y un número entero . El procedimiento debe buscar el elemento NUM y una vez encontrado visualizar todos sus antecesores (los anteriores).

capitulo vi Árboles y grafosvirtual.usalesiana.edu.bo/web/conte/archivos/285.pdf · Árboles y...

Documents