• Author / Uploaded
• irvyn

• Categories
• Lógica matemática
• Matemática aplicada
• Ciencias de la computación teórica
• Gestión de datos
• Áreas de la informática

Citation preview

ESTRUCTURA DE DATOS

ITP

Árboles binarios •

Un árbol binario es un árbol en el que ningún nodo puede tener más de dos sub árboles binario, cada nodo puede tener, cero, uno o dos hijos (sub árboles). Se conoce el nodo de como hijo izquierdo y el nodo de la derecha como hijo derecho.

•

Se define un árbol binario como un conjunto finito de elementos (nodos) que bien está vació o está formado por una raíz con dos árboles binarios disjuntos, llamados subárbol izquierdo y derecho de la raíz.

•

Definición recursiva: Un árbol binomial de orden 0 es un nodo. Un árbol binomial de orden k tiene una raíz de grado k y sus hijos son raíces de árboles binomiales de orden k-1,

k-

2,..., 2, 1, 0 (en ese orden). Un árbol binomial de orden k tiene 2k nodos, y altura k. Por su estructura, un árbol binomial de orden k puede ser construido a partir de dos árboles de orden k-1 en forma trivial, agregando uno de ellos como el hijo más a la izquierda del otro.

En los apartados que siguen se considerarán únicamente árboles binarios y, por lo tanto, se utilizará la palabra árbol para referirse a árbol binario. Los árboles de grado superior a 2 reciben el nombre de árboles multicamino. Árbol binario de búsqueda.- Los árboles binarios se utilizan frecuentemente para representar conjuntos de datos cuyos elementos se identifican por una clave única. Si el árbol está organizado de tal manera que la clave de cada nodo es mayor que todas las claves su subárbol izquierdo, y menor que todas las claves del subárbol derecho se dice que este árbol es un árbol binario de búsqueda.

Nota

Página 1

ESTRUCTURA DE DATOS

ITP

Un árbol binario no puede tener más de dos sub árboles. Un árbol binario es una estructura recursiva. Cada nodo es la raíz de su propio subárbol y tiene hijos, que son raíces de árboles llamados los sub árboles derecho e izquierdo del nodo, respectivamente.

REPRESENTACIÓN DE ARBOLES BINARIOS

Los arboles binarios pueden ser representados de dos modos diferentes: --Mediante punteros --Mediante arrays. REPRESENTACIÓN POR PUNTEROS

Cada nodo de un árbol será un registro que contiene al menos tres campos:

•

Un campo de datos con un tipo de datos

•

Un puntero al nodo subárbol izquierdo (que puede ser nulo)

•

Un puntero al nodo del subárbol izquierdo (que puede ser nulo).

Este algoritmo seria: Struct arbol{ datos; Struct arbol *ptrizq; Struct arbol *ptrder; };

Estructura de un árbol binario La estructura de un árbol binario se construye con nodos. Cada nodo debe contener el campo dato (datos a almacenar) y dos campos punteros, uno subárbol izquierdo y otro al subárbol derecho, que se conocen como puntero izquierdo (izquierdo, izdo.) y puntero derecho (derecho, dcho.) respectivamente. Un valor NULL indica un árbol vacío.

Página 2

ESTRUCTURA DE DATOS

ITP

Implementación de un nodo de un árbol binario de búsqueda Un árbol binario de búsqueda se puede utilizar cuando se necesita que la información se encuentre rápidamente. Estudiemos un ejemplo de árbol binario en el que cada nodo contiene información relativa a una persona. Cada nodo almacena un nombre de una persona y el número de matrícula en su universidad (dato entero). Declaración de tipos Nombre Matricula struct nodo { int nummat; char nombre [ 30 ] ; struct nodo *izda, *dcha; }; typedef struct nodo Nodo;

Creación de un nodo La función tiene como entrada un dato entero que representa un número de matrícula y el nombre. Devuelve un puntero al nodo creado. Nodo* CredrNodo ( int id, char* n) { Nodo* t ; L = (Nodo*) malloc(sizeof (Nodo)); L->nummdt = id; ctrcpy(t->nombre,n); t ->izdd = t - > dchd = NULL; r e t u r n t; }

En java package arbolbinario; public class Nodo { protected Object dato;

Página 3

ESTRUCTURA DE DATOS

ITP

protected Nodo izdo; protected Nodo dcho; public Nodo(Object valor) { dato=valor; izdo=dcho=null; } public Nodo(Nodo rama izdo, objet valor,nodo ramadcho) { this( dato) ; izdo=ramaizdo; dcho0=ramadcho; } //operaciones de acceso public objet valornodo(){return valor;} public Nodo subarbolIzdo (){return izdo;} public Nodo subarbolDcho (){return dcho;} public void nuevoValor(objet d){dato=d;} public void ramaIzdo(Nodo n){izdo=n;} public void ramaDcho(Nodo n){dcho=n;} }

Clasificación de Arboles Binarios

Existen cuatro tipos de árbol binario: •

Árbol Binario enhebrado.

•

Árbol Binario Completos.

•

Árbol Binario degenerado

•

Árbol Binario lleno.

•

Árbol Binario hilvanado.

•

Árbol Binario heterogéneo.

A continuación se hará una breve descripción de los diferentes tipos de árbol binario así como un ejemplo de cada uno de ellos.

Árboles binarios enhebrados Página 4

ESTRUCTURA DE DATOS

ITP

Los árboles enhebrados son una representación ideada por A.J. Perlis y C. Thornton en el año 1960, que permite implementar los recorridos sin necesidad de espacio adicional (como mucho, un par de booleanos de marca en cada nodo), y se basa en la propiedad ya conocida de que una representación encadenada normal de los árboles desaprovecha muchos apuntadores que no apuntan a ningún nodo. En el caso binario, de los 2n encadenamientos existentes en un árbol de n nodos hay exactamente n+1 sin usar. Por ello, es bueno plantearse si se pueden reciclar estos apuntadores para llevar a cabo cualquier otra misión, y de ahí surge el concepto de hebra: cuando un nodo no tiene hijo derecho, se sustituye el valor nulo del encadenamiento derecho por su sucesor en orden, y cuando no tiene hijo izquierdo, se sustituye el valor nulo del encadenamiento izquierdo por su predecesor en orden; de esta manera, se favorece la implementación de los recorridos sobre el árbol.

Árbol binario completo Un árbol binario completo de profundidad n es un árbol en el que para cada nivel, del O al nivel n-1 tiene un conjunto lleno de nodos y todos los nodos hoja a nivel n ocupan las posiciones más a la izquierda del árbol. Un árbol binario completo que contiene 2" nodos a nivel n es un árbol lleno. Un árbol lleno es un árbol binario que tiene el máximo número de entradas para su altura. Esto sucede cuando el último nivel está lleno.

Página 5

ESTRUCTURA DE DATOS

ITP

Árbol binario degenerado

Árbol es un tipo especial denominado árbol degenerado en el que hay un solo nodo hoja (E) y cada nodo no hoja sólo tiene un hijo. Un árbol degenerado es equivalente a una lista enlazada.

Árbol binario lleno Los árboles binarios y llenos de profundidad ki-1 proporcionan algunos datos matemáticos que es necesario comentar. En cada caso, existe un nodo (2") al nivel O (raíz), dos nodos (2') a nivel 1, cuatro nodos (2') a nivel 2, etc. A través de los primeros k-I niveles hay 2'-I nodos. 1 + 2 + 4 +... + 2k = 2k-1 A nivel k, el número de nodos adicionados para un árbol completo está en el rango de un mínimo de 1 a un máximo de 2L (lleno). Con un árbol lleno, el número de nodos es 1 + 2 + 4 +... + 2k + 2k = 2k+1 -1 El número de nodos n en un árbol binario completo de profundidad k+1 (0 a k niveles) cumple la desigualdad

2k≤n≤2k+1-1 hijo-dcho.) ; if (profundidad1 ’> profimdidad2) else return profundidad1 + 1; return profundidad2 + 1; } }

Determinación de la altura de un árbol La altura de un árbol dependerá del criterio que se siga para definir dicho concepto. Así, si en el caso de un árbol que tiene nodo raíz, se considera que su altura es 1, la altura del árbol es 2, y la altura del árbol es 4. Por último, si la altura de un árbol con un nodo es 1, la altura de un árbol vacío (el puntero es NULL) es O.

Página 9

ESTRUCTURA DE DATOS

ITP

Función que determina la altura de un árbol binario de manera recursiva. Se considera que la altura de un árbol vacío es O; si no está vacío. La altura es I + máximo entre las alturas de rama izquierda y derecha. int altura(Nodo* r) { if (r == NULL) return 0; else return (1 + max(alturd(r-zizda),altura(r>dcha)))); }

Recorrido de un árbol binario •

Recorrido en profundidad

•

Recorrido en nivel

•

Recorre el árbol por sub árboles hay tres formas: Pre orden, in orden y post orden.

Recorrido por niveles de los árboles binarios El recorrido por niveles o por anchura de un árbol binario consiste en visitar primero la raíz del árbol, después los nodos que están en el nivel 2, después los que están en el nivel 3, etc., hasta visitar los nodos del último nivel del árbol; para cada nivel, los nodos se visitan de izquierda a derecha. Recorridos en profundidad de los árboles binarios

Dado el árbol binario a∈ A2v, se definen tres recorridos en profundidad: - Recorrido en pre orden (pre orden trasversal): Si a es el árbol vacío, termina el recorrido; si no lo es, primero se visita la raíz de a y, a continuación, se recorren en pre orden los subárboles izquierdo y derecho. - Recorrido en orden (en orden trasversal): Página 10

ESTRUCTURA DE DATOS

ITP

si a es el árbol vacío, termina el recorrido; si no lo es, primero se recorre en orden el subárbol izquierdo de a, a continuación, se visita su raíz y, por último, se recorre en orden el subárbol derecho de a. - Recorrido en postorden (postorden trasversal): si a es el árbol vacío, termina el recorrido; si no lo es, primero se recorren en postorden sus subárboles izquierdo y derecho y, a continuación, se visita su raíz. Pre orden (crea) = crea Pre orden (enraíza (a1, v, a2)) = Concatena (concatena (inserta (crea, v), pre orden (a1)), pre orden (a2)) En orden (crea) = crea En orden (enraíza (a1, v, a2)) = concatena (inserta (enorden (a1), v), enorden (a2)) Postorden (crea) = crea Postorden (enraíza (a1, v, a2)) = inserta (concatena (postorden (a1), postorden (a2)), v)

•

Recorrido pre orden

El recorrido pre orden (NID) conlleva los siguientes pasos, en los que el raíz va antes que los sub árboles: 1. Recorrer la raíz (N). 2. Recorrer el subárbol izquierdo (I) en pre orden. 3. Recorrer el subárbol derecho (D) en pre orden. Dado las características recursivas de los árboles, el algoritmo de recorrido tiene naturaleza recursiva. Primero, se procesa la raíz, a continuación el subárbol izquierdo y a continuación el subárbol derecho. Para procesar el subárbol izquierdo, se hace una llamada recursiva al procedimiento pre orden y luego se hace lo mismo con el subárbol derecho. El algoritmo recursivo correspondiente para un árbol T es: Si T no es vacio entonces Inicio Ver los datos en la raíz de T Pre orden (subárbol izquierdo de la raíz de T) Pre orden (subárbol derecho de la raíz de T) Fin Regla En el recorrido pre orden, la raíz se procesa antes que los sub árboles izquierdo y derecho.

Página 11

ESTRUCTURA DE DATOS

ITP

Si utilizamos el recorrido pre orden del árbol de la Figura se visita primero el raíz (nodo A). A continuación se visita el subárbol izquierdo de A, que consta de los nodos B, D y E. Dado que el subárbol es a su vez un árbol, se visitan los nodos utilizando el orden NID. Por consiguiente, se visita primero el nodo B, después D (izquierdo) y, por último, E (derecho).

•

Recorrido en orden

El recorrido en orden procesa primero el subárbol izquierdo, después el raíz y a continuación el subárbol derecho. El significado de in es que la raíz se procesa entre los sub árboles. Si el árbol no está vacío, el método implica los siguientes pasos: 1. Recorrer el sub árbol izquierdo (1) en orden. 2. Visitar el nodo raíz (N). 3. Recorrer el subárbol derecho ( I ) ) en orden. El algoritmo correspondiente es: En orden(A) Si el árbol no esta vacio entonces •

Inicio

•

Recorrer el subárbol izquierdo

•

Visitar el nodo raíz

•

Recorrer el subárbol derecho

•

Fin

Un refinamiento del algoritmo es:

Página 12

ESTRUCTURA DE DATOS

ITP

Algoritmo en orden (valor raíz )

•

Recorrer un árbol binario en la secuencia izquierdo-nodo-derecho

•

Pre raíz en el nodo de entrada de un árbol o subárbol

•

Post cada nodo se ha de procesar en orden

1 si (raíz no es nula)

1. En orden (raíz -> subárbol izquierdo) 2. procesar (raíz) 3. En orden (raíz->subárbol derecho) 2 retorno Fin enorden

•

Recorrido post orden

El recorrido post orden (IDN) procesa el nodo raíz (post) después de que los sub árboles izquierdo y derecho se han procesado. Se comienza situándose en la hoja más a la izquierda y se procesa. A continuación se procesa su subárbol derecho. Por último se procesa el nodo raíz. Las etapas del algoritmo son: 1. Recorrer el subárbol izquierdo (I) en post orden. 2. Recorrer el subárbol derecho (D) en post orden. 3. Visitar el nodo raíz (N). El algoritmo recursivo para un árbol A es: Si A no esta vacio entonces Inicio Post orden (subárbol izquierdo del raíz de A)

Página 13

ESTRUCTURA DE DATOS

ITP

Post orden (subárbol derecho del raíz de A) Visitar la raíz de A Fin El refinamiento del algoritmo es: Algoritmo post orden (valor raíz ) •

Recorrer un árbol binario en secuencia izquierda-derecha-nodo

•

Pre raíz es el nodo de entrada de un árbol a un subárbol

•

Post cada nodo ha sido procesado en orden

1. Si (raíz no es nulo) 1.

Post Orden (raíz -> Sub árbol izquierdo)

2.

Post Orden (raíz -> Sub árbol Derecho)

3.

procesar (raíz)

1. retorno Fin post orden

Códigos en java //recorridos en un árbol binario en preorden public static void preorden(Nodo r) { If(r! =null) { r.visitar (); Preorden (r.ubarbolizdo ()); Preorden (r.subarboldcho ());

Página 14

ESTRUCTURA DE DATOS

ITP

} }

//recoridos en un arbol binario en inorden public static void inorden(Nodo r) { if(r!=null) { inorden(r.ubarbolizdo()); r.visitar(); inorden(r.subarboldcho()); } }

//recoridos en un arbol binario en postorden public static void postorden(Nodo r) { if(r!=null) { postorden(r.ubarbolizdo()); postorden(r.subarboldcho()); r.visitar(); } }

ÁRBOL BINARIO DE BÚSQUEDA Los árboles vistos hasta ahora no tienen un orden definido; sin embargo, los árboles binarios ordenados tienen sentido. Estos árboles se denominan árboles binarios de búsqueda, debido a que se pueden buscar en ellos un término utilizando un algoritmo de búsqueda binaria similar al empleado en arrays. Un árbol binario de búsqueda es aquel que dado un nodo, todos los datos del subárbol izquierdo son menores que los datos de ese nodo, mientras que todos los datos del subárbol derecho son mayores que sus propios datos.

Página 15

ESTRUCTURA DE DATOS

ITP

Operaciones básicas en arboles binarias. •

Función inserta

•

Función eliminar

•

Función eliminar árbol

•

Visita a los nodos de un árbol (si los hay)

Función insertar ( ) La función insertar que pone nuevos nodos es sencilla. Se deben declarar tres argumentos: un puntero al raíz del árbol, el nuevo nombre y número de matrícula de la persona. La función creará un nuevo nodo para la nueva persona y lo inserta en el lugar correcto en el árbol de modo que el árbol permanezca como binario de búsqueda. La operación de inserción de un nodo es una extensión de la operación de búsqueda. Los pasos a seguir son:

1. Asignar memoria para una nueva estructura nodo. 2. Buscar en el árbol para encontrar la posición de inserción del nuevo nodo, que se colocará como nodo hoja. 3. Enlazar el nuevo nodo al árbol. El código C de la función: void insertar (Nodo** raiz, int nuevomat, char *nuevo-nombre) { if ( ! (*raiz)) else if (nuevomat i (*raiz) -> nummat) else *raiz = CrearNodo(nuevo-mat, nuevo-nombre) ; insertar (&((*raiz) -> izda), nuevomat, nuevo-nombre); insertar ( & ( (*raiz) -> dcha), nuevomat, nuevo-nombre);

Página 16

ESTRUCTURA DE DATOS

ITP

}

En java public void insertar(object valor) throws exceptions { Comparador dato; dato=(Comparador)valor; raiz=insertar(raiz, dato ); } //metodo interno para realizar la operacion protected nodo insertar(nodo raizSub, Coparador dato)throws exceptions { if(raizSub==null) raizSub=new nodo(dato); elseif(dato.menorque(raizSub.valornodo())) { nodo iz; iz=insertar(raizSub.subarbolizdo(),dato); raizSub.ramaizdo(iz); } else if(dato.mayorque(raizSub.valornodo())) { nodo dr; dr=insertar(raizSub.subarboldcho(),dato); raizSub.ramadcho(dr); } else throws new exceptions("nodo duplicado") return raizSub(); }

Eliminación eliminar ()

Página 17

ESTRUCTURA DE DATOS

ITP

El árbol resultante es: La operación de eliminación de un nodo es también una extensión de la operación de búsqueda, si bien más compleja que la inserción debido a que el nodo a suprimir puede ser cualquiera y la operación de supresión debe mantener la estructura de árbol binario de búsqueda después de la eliminación de datos. Los pasos a seguir son: 1. Buscar en el árbol para encontrar la posición de nodo a eliminar. 2. Reajustar los punteros de sus antecesores si el nodo a suprimir tiene menos de 2 hijos, o subir a la posición que éste ocupa el nodo más próximo en clave (inmediatamente superior o inmediatamente inferior) con objeto de mantener la estructura de árbol binario. Suprimir el elemento de clave 36 del siguiente árbol binario de búsqueda:

Resulta

void eliminar (Nodo** r, int mat) if ( ! (*r)) printf("!! Registro con clave %d no se encuentra ! ! . \n",mat); else if (mat i (*r)->nummat) eliminar ( & (*r)- >i.zda, mat) ; else if (mat > (*r)->numat) eliminar(&(*r)->dcha,mat); else / * Matricula encontrada * / {Nodo* q; / * puntero al nodo a suprimir * / q = (*r); if (q->izda == NULL){

Página 18

ESTRUCTURA DE DATOS

ITP

(*r) = q->dcha; else if (q->dcha == NULL) (*r) = q->izda; else { /* tiene rama izda y dcha. Se reemplaza por el mayor de los menores * /} Nodo* a, *p; P = q; a = q->izda; while (a->dcha) { p = a; a = a->dcha; } q->nummat = a->nummat; strcpy(q->nombre,a->nombre); if (p == q) p->izda = a->izda; else p->dcha = a->izda; q = a; } free(q) ; }

En java public void eliminar(object valor)throws exceptions { comparador dato; dato=(comprador)valor; raiz=eliminar(raiz,dato); } //metodo interno para realizar la operacion elimnar(Nodo raizSub,comparador dato) throws exceptions { if(raizSub==null) throws new exceptions("no encontrado elndo on clave"); else if(dato.menorque(raizSub.valornodo()))

Página 19

ESTRUCTURA DE DATOS

ITP

{ nodo iz; iz=insertar(raizSub.subarbolizdo(),dato); raizSub.ramaizdo(iz); } else if(dato.mayorque(raizSub.valornodo())) { nodo dr; dr=insertar(raizSub.subarboldcho(),dato); raizSub.ramadcho(dr); } else//nodo encontrado { Nodo q; q=raizSub;//nodo a quitar del arbol if(q.subarbolizdo()==null) raizSub=q.subarbldcho(); else if(q.subarboldcho()==null) raizSub=q.subarbolizdo(); else { q=reemplazar(q);//tiene rama izquierda y derecha } q=null; , } return raizSub; } //metodo pr sustituir por el mayor de los menores private Nodo reeemplazar(Nodo act) { Nodo a,p; p=act;

Página 20

ESTRUCTURA DE DATOS

ITP

a=act.subarbolizdo(); while(a.subarboldcho()!=null) { p=a a=a.subarboldcho(); } act.nuevoValor(a.valornodo()); if(p==act) p.ramaizdo(a.subarbolizdo()); else p.ramadcho(a.subarboldcho()); return a; }

Visita a los nodos de un árbol En muchas aplicaciones se desea explorar (recorrer) los nodos de un árbol pero sin tener en cuenta un orden de recorrido preestablecido. En esos casos, el cliente o usuario es libre para utilizar el algoritmo oportuno. La función Contar Hojas recorre el árbol y cuenta el número de nodos hoja. Para realizar esta operación se ha de visitar cada nodo comprobando si es un nodo hoja. El recorrido utilizado será el Postorden.

/ * Función ContarHojas la función utiliza recorrido postorden en cada visita se comprueba si el nodo es un nodo hoja (no tiene descendientes) */ void contarhojas (Nodo" r, int* nh) { if (r != NULL) { contarhojas (r -> izda, nh) ; contarhojas (r -> dcha, nh) ;

Página 21

ESTRUCTURA DE DATOS

ITP

/ * procesar raíz: determinar si es hoja * / if (r->izda==NULL && r->dcha==NULL) (*nh)++; } }

La función elimina árbol Utiliza un recorrido postorden para liberar todos los nodos del árbol binario. Este recorrido asegura la liberación de la memoria ocupada por un nodo después de haber liberado su rama izquierda y derecha. / * Función eliminar árbol Recorre en postorden el árbol. Procesar la raíz, en esta Función es liberar el nodo con free (). */ void eliminarbol (Nodo" r) { if (r != NULL) i eliminarbol(r -> izda); eliminarbol(r -> dcha); printf ("\tNodob orrado: %d ",r->numat); free(r); } } Búsqueda La búsqueda de un nodo comienza en el nodo raíz y sigue estos pasos : 1. La clave buscada se compara con la clave del nodo raíz. 2. Si las claves son iguales, la búsqueda se detiene. 3. Si la clave buscada es mayor que la clave raíz, la búsqueda se reanuda en el subárbol derecha. Si la clave buscada es menor que la clave raíz, la búsqueda se reanuda con el subárbol izquierdo.

Buscar una información específica Si se desea encontrar un nodo en el árbol que contenga la información sobre una persona específica. La función buscar tiene dos parámetros, un puntero al árbol y un número de matrícula para la persona requerida. Como resultado, la función devuelve un puntero al nodo en el que se

Página 22

ESTRUCTURA DE DATOS

ITP

almacena la información sobre esa persona; en el caso de que la información sobre la persona no se encuentra se devuelve el valor O. El algoritmo de búsqueda es el siguiente: 1. Comprobar si el árbol está vacío. En caso afirmativo se devuelve O. Si la raíz contiene la persona, la tarea es fácil: el resultado es, simplemente, un puntero a la raíz. 2. Si el árbol no está vacío, el subárbol específico depende de que el número de matrícula requerido es más pequeño o mayor que el número de matrícula del nodo raíz. 3. La función de búsqueda se consigue llamando recursivamente a la función buscar con un puntero al subárbol izquierdo o derecho como parámetro. El código C de la función buscar. Es: Nodo* buscar (Nodo* p, int buscado) { if ( ! p ) else if (buscado == p -> nummdt) else if (buscado < p -> nummdt) else / return O; return p; return buscar (p ->izda , buscado); return buscar (p -> dcha, buscado); }

En java package arbolbinarioOrdenado; public interface comparador { boolean igualque(object q); boolean menorque(object q); boolean menorigualque(object q); boolean mayorque(object q); boolean mayorigualque(object q); } public Nodo buscar(object buscado) { comparador dato;

Página 23

ESTRUCTURA DE DATOS

ITP

dato=(comparador)buscado; if(raiz==null) return null; else return localizar(raizArbol(),dato); } protected Nodo localizar(Nodo raizSub,Comparador buscado) { if (raizSub==null) return null; else if (buscado.igualque(raiz.Sub.valornodo())) return raiz; else if (buscado.menorque(raiz.Sub.valornodo())) return localizar(raizSub.subarbolizdo(),buscado); else return localizar(raizSub.subarboldcho(),buscado); } public Nodo bucariterativa(object buscado) { comparador dato; boolean encontrado=false; Nodo raizSub=raiz; dato=(comparador)buscado;

while(!enconrado && raizSub=!=null) { if (dato.igualque(raiz.Sub.valornodo()) encontrado=true; else if (dato.menorque(raiz.Sub.valornodo()) raizSub=raizSub.subarbolizdo(); else raizSub=raizSub.subarboldcho(); } return raizSub; }

Página 24

ESTRUCTURA DE DATOS

ITP

Arboles por montón Definición: El Árbol en Montón consiste en el ordenamiento de un conjunto de Elemento en un solo arreglo. Inserción Definición: El Concepto de Inserción ya es familiar para nosotros y sabemos que para realizar el mismo no resulta complejo el procedimiento. Pero en los Árboles en Montón es uno de los Métodos más largos para efectuarlo. Detalle: Básicamente lo que hace estos Algoritmos es la Inserción Ordenada. Primero comparan si es posible insertar algún Elemento al Arreglo, si es posible hacerlo Ingresa el Elemento a la Ultima posición. Después básicamente acomoda el Arreglo con el Método de la Burbuja llamando a otra serie de Métodos. Algoritmos:

Insertar(Arbol, N, Elemento) Si N a N -> N + 1 OrdMon(Arbol, N) Salir //Fin de la condición// Imprimir "Árbol Lleno..." Salir OrdMon(Arbol, Total) ConstMon(Arbol, Total) Mientras Total > 1 Total -> Total - 1 Burbuja(0, Total) RecMon(Total, 0) //Fin del ciclo// Salir ConstMon(Arbol, Total) v -> (Total/2) - 1

Página 25

ESTRUCTURA DE DATOS

ITP

Mientras v ≥ 0 RecMon(Arbol, Total, v) v -> v - 1 //Fin del ciclo// Salir ---RecMon(Arbol, Total, v) w -> 2*v+1 Mientras w < Total Si (w+1) < Total Si Arbol[w+1] > Arbol[w] w++ //Fin de la condición// Fin de la condición Si Arbol[v] ≥ Arbol[w] Salir //Fin de la condición// Burbuja(Arbol, v, w) v -> w w -> 2*v+1 //Fin del ciclo// Salir ---Burbuja(Arbol, v, w) t -> Arbol[v] Arbol[v] -> Arbol[w] Arbol[w] -> t Salir Diagrama:

Búsqueda Definición: El Concepto de Búsqueda es sencillo, simplemente es un método de búsqueda lineal. Existen 3 posible resultados: 1. Que el Árbol este Vació y no se puede realizar la búsqueda.

Página 26

ESTRUCTURA DE DATOS

ITP

2. Que el Elemento sea encuentre en el Árbol 3. Que el Elemento no este dentro del Árbol Detalle: Se manda al Método Búsqueda el Dato que se desea buscar, se acomoda el Árbol en Orden en caso que no estuviera Ordenado y después compara con cada uno de los datos. Algoritmos:

**Busqueda(Arbol, N, Elemento)** Si N ≠ 0 OrdMon(Arbol, N) i -> Mientras i < N;i++) Si Arbol[i] = Elemento Imprimir "Elemento Encontrado..." Salir //Fin de la condición// i -> i + 1 //Fin del ciclo// Imprimir "El Elemento no esta en el Árbol..." Salir //Fin de la condición// Imprimir "Árbol Vació..." Salir

Diagrama:

Eliminación Definición: El Concepto de Eliminación consiste en la búsqueda de un Elemento y sacarlo del Arreglo. Existen 3 casos Diferentes; 1. Que el Árbol este Vació y no se puede realizar la eliminación 2. Que el Elemento sea encuentre en el Árbol y sea eliminado 3. Que el Elemento no este dentro del Árbol por lo tanto no se elimina

Página 27

ESTRUCTURA DE DATOS

ITP

Detalle: Vemos si el Árbol tiene Elementos insertados en el, de otra forma será imposible realizar la Eliminación ya que esta Vació. Después si el Árbol tiene Elementos lo ordenamos y hacemos un búsqueda lineal para encontrar el dato. Después usamos el método de la Burbuja para dejar el Elemento Eliminado hasta el final y le Restamos a N un Elemento. Algoritmo:

Eliminar(Arbol, N, Elemento) Si N ≠ 0 OrdMon(Arbol, N) i -> Mientras I < N Si Arbol[i] = Elemento j -> i + 1 Mientras j < N t -> Arbol[i] Arbol[i] -> Arbol[j] Arbol[j] -> t j -> j + 1 //Fin del ciclo// N -> n - 1 Imprimir "Elemento Eliminado..." Salir //Fin de la condición// i -> i + 1 //Fin del ciclo// Fin de la condición Imprimir "Arbol Vacio... Imposible Eliminar..." Salir

Diagrama:

Recorrido (Ordenado) Definición: El Recorrido simplemente ira desplegando cada uno de los Elementos del Árbol. Solo existen 2 posibles casos:

Página 28

ESTRUCTURA DE DATOS

ITP

1. Que el Árbol este Vació y no se pueda recorrer 2. El Árbol tenga Elementos para desplegar Detalle: Comparamos para comprobar que el Árbol tiene Elementos dentro de el, de ser así Desplegamos cada uno de ellos. De otra manera Desplegamos Árbol Vació. Algoritmo:

Recorrido (Arbol, N) Si N ≠ 0 i -> Mientras i < N Imprimir Arbol[i] i -> i + 1 //Fin del ciclo// Salir //Fin de la condición// Imprimir "Arbol Vacio..." Salir

Ordenación mediante montones Se puede usar una cola de prioridad para ordenar N elementos insertándolos en un montículo binario y extrayéndolos llamando a suprimir () N veces. O(N log N) en el caso peor.

Un montículo binomial es similar a un montículo binario, pero soporta eficientemente la fusión de dos montículos.

MAXIMOS Y MINIMOS DE UN ARBOL POR MONTON

EJEMPLO SAQUE EL MAXIMO Y MINIMO DEL SIGUIENTE ARBOL

Máximos de un árbol por montón Página 29

ESTRUCTURA DE DATOS

ITP

La raíz será mayor que los dos hijos. •

HIJO IZQUIERDO izda = t-> dcha = NULL; return t ; } Nodo* buscar (Nodo* p, int buscado) if ( ! p ) else if (buscado == p -> nummat) return p; else if (buscado < p -> nummat) return buscar (p -> izda, buscado); else return buscar (p -> dcha, buscado); } void insertar (Nodo** raiz, int nuevomat, char *nuevo-nombre) i if ( ! ("raiz)) *raiz = CrearNodo(nuevomat, nuevo-nombre); else if (nuevomat i (*raiz) -> nummat) insertar (&((*raiz) -> izda), nuevomat, nuevo-nombre); else insertar (&((*raiz) -> dcha), nuevo-mat, nuevo-nombre); } void visualizar (Nodo" r) { if (r) { visualizar(r -> izda); printf('Matricu1a %d \t %s \n",r->nummat,r->nombre); visualizar(r -> dcha); }} void eliminar (Nodo** r, int mat) if ( ! (*r)) printf("!! Registro con clave %d no se encuentra ! ! . \n",mat); else if (mat i (*r)->nummat) eliminar ( & (*r)- >i.zda, mat) ;

Página 33

ESTRUCTURA DE DATOS

ITP

else if (mat > (*r)->numat) eliminar(&(*r)->dcha,mat); else / * Matricula encontrada * / {Nodo* q; / * puntero al nodo a suprimir * / q = (*r); if (q->izda == NULL){ (*r) = q->dcha; else if (q->dcha == NULL) (*r) = q->izda; else { /* tiene rama izda y dcha. Se reemplaza por el mayor de los menores * /} Nodo* a, *p; P = q; a = q->izda; while (a->dcha) { p = a; a = a->dcha; } q->nummat = a->nummat; strcpy(q->nombre,a->nombre); if (p == q) p->izda = a->izda; else p->dcha = a->izda; q = a; } free(q) ; }

En java import java.awt.Color; import java.awt.Container; import java.awt.FlowLayout; import java.awt.Font; import java.awt.TextArea; import java.awt.event.ActionEvent; import java.awt.event.ActionListener;

Página 34

ESTRUCTURA DE DATOS

ITP

import javax.swing.*; public class PruebaArbol extends JFrame { Container c=getContentPane(); private JMenuBar menu; private JMenu i1,i2; private JMenuItem construye,mostrar,alt,hoj,anc,salir,creditos,nuevo,inor,pos,pre; private int dato=0,nodos=0; Arbol arbol; String aux="R",fila=" ",columna=" ",cadena=new String(); private TextArea most; public PruebaArbol(String cogollo) { super(cogollo); c.setLayout(new FlowLayout()); menu = new JMenuBar(); i1 = new JMenu("ARCHIVO"); i2 = new JMenu("PROCESOS"); nuevo=new JMenuItem("NUEVO PROYECTO"); salir=new JMenuItem("SALIR"); construye=new JMenuItem("CONSTRUIR ARBOL"); mostrar=new JMenuItem("MOSTRAR ARBOL"); alt=new JMenuItem("ALTURA DEL ARBOL"); hoj=new JMenuItem("HOJAS DEL ARBOL"); anc=new JMenuItem("ANCESTROS DEL ARBOL"); inor=new JMenuItem("INORDEN"); pre=new JMenuItem("PREORDEN"); pos=new JMenuItem("POSORDEN"); creditos=new JMenuItem("CREDITOS"); i1.add(nuevo); i1.add(construye); i1.add(mostrar); i1.add(creditos); i1.add(salir); i2.add(alt); i2.add(hoj); i2.add(anc);

Página 35

ESTRUCTURA DE DATOS

ITP

i2.add(inor); i2.add(pos); i2.add(pre);

nuevo.addActionListener(new manejaEventos()); salir.addActionListener(new manejaEventos()); mostrar.addActionListener(new manejaEventos()); construye.addActionListener(new manejaEventos()); alt.addActionListener(new manejaEventos()); anc.addActionListener(new manejaEventos()); hoj.addActionListener(new manejaEventos()); inor.addActionListener(new manejaEventos()); pre.addActionListener(new manejaEventos()); pos.addActionListener(new manejaEventos()); creditos.addActionListener(new manejaEventos()); menu.add(i1); menu.add(i2); c.setBackground(new Color(128,0,255)); setJMenuBar(menu); setSize( 1024 , 768 ); setVisible( true ); }

class manejaEventos implements ActionListener { public void actionPerformed(ActionEvent e) { if(e.getSource()==construye){

arbol=new Arbol(); int valor=0; nodos=Integer.parseInt( JOptionPane.showInputDialog(null,"ingrese el numero de nodos para el arbol") );

Página 36

ESTRUCTURA DE DATOS

ITP

for (int i=1;i