Arboles
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Arboles as PDF for free.
More details
- Words: 6,367
- Pages: 47
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<2k+1 Aplicando logaritmos a la ecuación con desigualdad anterior klogzn
Página 6
ESTRUCTURA DE DATOS
ITP
Por ejemplo, un árbol lleno de profundidad 4 (niveles O a 3) tiene 24-1 -1= 15 nodos.
Árbol binario interhilvanados derechos
Este tipo de árbol sus últimos niveles de subárboles no apuntan hacia nulo sino que se unen con hilos punteados sustituyéndolos a estos apuntadores en los nodos con subárboles derechos vacios. Esto se denomina arboles interhilvanados derechos.
* 12
+ 3 4
1
Árbol binario heterogéneo
A menudo, la información que contiene diferentes nodos de árbol binario no es todo del mismo tipo. Por ejemplo, al representar una expresión binaria con operándos numéricos constantes, pretendemos usar un árbol binario cuyas hojas contengan números, pero cuyos nodos no contengan operadores que presentan caracteres .La figura muestra este tipo de árbol binario.
Página 7
ESTRUCTURA DE DATOS
ITP
+ * 12
/ 3 4
1
Operaciones básicas con arboles binarios
•
Una tarea muy común a realizar con un árbol es ejecutar una determinada operación con cada uno de los elementos del árbol. Esta operación se considera entonces como un parámetro de una tarea más general que es la visita de todos los nodos o, como se denomina usualmente, del recorrido del árbol.
•
Puede haber muchas tareas a realizar con una estructura de árbol; una de corriente es ejecutar una operación P con cada uno de los elementos del árbol. P se considera entonces como un parámetro de una tarea mas general que es la visita a los nodos o, como se denomina usualmente, del recorrido del árbol.
•
Se aplican varias operaciones primitivas a n árbol binario. Si p es un apuntador a un nodo de un árbol binario, la función info(p) retorna el contenido de nodo. Las funciones left(p), rigth(p), father(p), brother(p); retornan apuntadores al hijo izquierdo de nodo , al hijo derecho de nodo , al padre de nodo y así respectivamente. Estas funciones retornan al apuntador null si no tiene padre, hijo izquierdo, hijo derecho, o hermano.
Si se considera la tarea como un proceso secuencial, entonces los nodos individuales se visitan en un orden específico, y pueden considerarse como organizados según una estructura lineal. De hecho, se simplifica considerablemente la descripción de muchos algoritmos si puede hablarse del proceso del siguiente elemento en el árbol, según un cierto orden subyacente. Hay dos formas básicas de recorrer un árbol: El recorrido en amplitud y el recorrido en profundidad.
PROFUNDIDAD
Página 8
ESTRUCTURA DE DATOS
ITP
La profundidad de un árbol binario es una característica que se necesita conocer con frecuencia durante el desarrollo de una aplicación con árboles. La función Profundidad evalúa la profundidad de un árbol binario. Para ello tiene un parámetro que es un puntero a la raíz del árbol. El desarrollo de una aplicación con árboles. La función Profundidad evalúa la profundidad de un árbol binario. Para ello tiene un parámetro que es un puntero a la raíz del árbol. El caso más sencillo de cálculo de la profundidad es cuando el árbol está vacío en cuyo caso la profundidad es O. Si el árbol no está vacío, cada subárbol debe tener su propia profundidad, por lo que se necesita evaluar cada una por separado. Las variables profundidad1, profundidad almacenarán las profundidades de los sub árboles izquierdo y derecho respectivamente. El método de cálculo de la profundidad de los sub árboles utiliza llamadas recursivas a la función Profundidad con punteros a los respectivos sub árboles como parámetros de la misma. La función Profundidad devuelve como resultado la profundidad del subárbol mas profundo más I (la misma de la raíz). int Profundidad (Nodo *p) { if (!p) else return O ; { int profundidad1 = Profundidad (p -> hijo-izqdo.); int profundidad2 = Profundidad (p -> 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<25 Arbol[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
•
HIJO DERECHO
SEGUNDO PASO
GG
CUARTO PASO
TERCER PASO
MINIMO DE UN ARBOL POR MONTON La raíz será menor que los dos hijos.
Página 30
ESTRUCTURA DE DATOS •
RAIZ
•
RAIZ
ITP
SEGUNDO PASO
ULTIMO PASO
Códigos
Árbol binario #include <stdio.h> #include <stdlib.h> #include struct nodo { int nummat; char nombre [ 3 O ] ; struct nodo *izda, *dcha; }; typedef struct nodo Nodo; Nodo* CrearNodo(int id, char* n ) ; Nodo* buscar (Nodo* p, int buscado); void insertar (Nodo** raiz, int nuevo-mat, chdr *nuevo-nombre);
Página 31
ESTRUCTURA DE DATOS
ITP
void eliminar (Nodo** r, int mat); void visualizar (Nodo* r); int main() { int nm; char nom[30] ; Nodo* R = O; / * Crea el árbol * / do { printf ("Numero de matricula (O -> Fin) : " ) ; scanf ("%d%*c", &nm) ; if (nm) { printf ("Nombre: " ) ; gets (nom) ; insertar(&R,nm,nom); } / * Opciones de escribir el árbol o borrar una registro * / }while (nmj; clrscr ( ) ; do { puts(" 1. Mostrar el árboi\n"); puts(“2. Eliminar un registro\n"); do scanf("%d%*c", &nm); while(nm
Página 32
ESTRUCTURA DE DATOS
ITP
Nodo * t ; t = (Nodo") malloc(sizeof(Nodo)); t -> nummat = id; strcpy(t->nombre,n); t -> 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<=nodos;i++){ dato=Integer.parseInt( JOptionPane.showInputDialog(null,"ingrese el dato a insertar en el arbol") ); arbol.insertarNodo(dato); } }//end construye if(e.getSource()==pre){ JOptionPane.showMessageDialog(null,"Preorden : "+arbol.preorden()); }//end preorden if(e.getSource()==inor){ JOptionPane.showMessageDialog(null,"Inorden : "+arbol.inorden()); }//end inorden if(e.getSource()==pos){ JOptionPane.showMessageDialog(null,"Posorden : "+arbol.posorden()); }//end posorden if(e.getSource()==alt){ JOptionPane.showMessageDialog(null,"Altura : "+arbol.altura(arbol.retornaraiz())); }//end altura if(e.getSource()==hoj){ JOptionPane.showMessageDialog(null,"Hojas : "+arbol.hojas(arbol.retornaraiz())); }//end hojas if(e.getSource()==anc){ int db=Integer.parseInt(JOptionPane.showInputDialog(null,"Ingrese el dato cuyos ancestros desea conocer")); JOptionPane.showMessageDialog(null,"Ancestro : "+arbol.ancestros(arbol.retornaraiz(),db)); }//end ancestros if(e.getSource()==mostrar){ mostrarArbol(arbol.retornaraiz(),aux); c.removeAll(); c.add(most); c.setBackground(Color.WHITE); c.repaint();
Página 37
ESTRUCTURA DE DATOS
ITP
}//end mostrar if(e.getSource()==nuevo){ c.removeAll(); arbol=new Arbol(); cadena=new String(); most=new TextArea(); dato=0;nodos=0; aux="R";fila=" ";columna=" "; c.setBackground(Color.WHITE); }//end nuevo if(e.getSource()==creditos){ c.removeAll(); JLabel cred=new JLabel("ESTE PROGRAMA FUE DISEÑADO POR JUAN RICARDO COGOLLO OYOLA"); cred.setBounds(###TELEFONO_CENSURADO###); cred.setFont(new Font("EuropeExt", Font.BOLD + Font.ITALIC, 14)); cred.setForeground(Color.DARK_GRAY); c.setBackground(Color.white); c.add(cred); c.repaint(); }
if(e.getSource()==salir){ System.exit(0); }//end salir
}}
public static void main(String[] args) { PruebaArbol ventana = new PruebaArbol("ARBOLES BINARIOS DE BUSQUEDA"); ventana.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); }
Página 38
ESTRUCTURA DE DATOS
ITP
void pintar(int d,String h){ cadena=cadena+columna+fila+h+" : "+String.valueOf(d); most = new TextArea("",200,300,0); most.setBounds(###TELEFONO_CENSURADO###); most.append(cadena); most.setEditable(false); } void mostrarArbol(NodoArbol R,String hijo){ String h=hijo; if(R!=null){ pintar(R.retornadato(),h);
if(R.li!=null){ aux="Izq"; fila=fila+" "; mostrarArbol(R.li,aux); int n=fila.length(); fila=fila.substring(10); } if(R.ld!=null){ aux="Der"; fila=fila+" "; mostrarArbol(R.ld,aux); int n=fila.length(); fila=fila.substring(10); } } }//end windows
}
Árbol en montón Página 39
ESTRUCTURA DE DATOS
ITP
#include #include class Arbol_Monton { private: int Arbol[25]; int N; public: Arbol_Monton() { for(int i=0;i<25;i++) Arbol[i]=0; N=0; } void Insertar(int a) { if(N<25) { Arbol[N]=a; N++; OrdMon(N); return;
Página 40
ESTRUCTURA DE DATOS
ITP
} cout<<"Arbol Lleno..."<<endl; } void Eliminar(int a) { int t; if(N!=0) { OrdMon(N); for(int i=0;i
Página 41
ESTRUCTURA DE DATOS
ITP
return; } } } cout<<"Arbol Vacio... Imposible Eliminar..."<<endl; } void Busqueda(int a) { if(N!=0) { OrdMon(N); for(int i=0;i
Página 42
ESTRUCTURA DE DATOS
ITP
void OrdMon(int n) { ConstMon(n); while(n>1) { n--; Burbuja(0,n); RecMon(n,0); } } void ConstMon(int n) { for(int v=n/2-1;v>=0;v--) RecMon(n,v); } void RecMon(int n,int v) { int w=2*v+1; while(w
Página 43
ESTRUCTURA DE DATOS
ITP
if (Arbol[w+1]>Arbol[w]) w++; if(Arbol[v]>=Arbol[w]) return; Burbuja(v,w); v=w; w=2*v+1; } } void Burbuja(int i,int j) { int t=Arbol[i]; Arbol[i]=Arbol[j]; Arbol[j]=t; } void Recorrido() { if(N!=0) { for(int i=0;i
Página 44
ESTRUCTURA DE DATOS
ITP
} cout<<"Arbol Vacio..."<<endl; } }tec; main() { int res,op=0; while(op!=5) { clrscr(); cout<<"\n1) Recorrido\n2) Busqueda\n3) Insercion\n4) Eliminar\n5) Salir"<<endl; gotoxy(1,1); cout<<"Que deseas hacer?: "; cin rel="nofollow">>op; gotoxy(1,10); switch (op) { case 1: tec.Recorrido(); break; case 2:
Página 45
ESTRUCTURA DE DATOS
ITP
cout<<"Que Numero deseas buscar?"<<endl; cin>>res; tec.Busqueda(res); break; case 3: cout<<"Que Numero quieres Insertar?"<<endl; cin>>res; tec.Insertar(res); break; case 4: cout<<"Que Numero quieres Eliminar?"<<endl; cin>>res; tec.Eliminar(res); break; case 5: cout<<"Salida..."; break; default: cout<<"Opcion Erronea"<<endl; break; } getch();
Página 46
ESTRUCTURA DE DATOS
ITP
} }
Página 47
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{
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<2k+1 Aplicando logaritmos a la ecuación con desigualdad anterior klogzn
Página 6
ESTRUCTURA DE DATOS
ITP
Por ejemplo, un árbol lleno de profundidad 4 (niveles O a 3) tiene 24-1 -1= 15 nodos.
Árbol binario interhilvanados derechos
Este tipo de árbol sus últimos niveles de subárboles no apuntan hacia nulo sino que se unen con hilos punteados sustituyéndolos a estos apuntadores en los nodos con subárboles derechos vacios. Esto se denomina arboles interhilvanados derechos.
* 12
+ 3 4
1
Árbol binario heterogéneo
A menudo, la información que contiene diferentes nodos de árbol binario no es todo del mismo tipo. Por ejemplo, al representar una expresión binaria con operándos numéricos constantes, pretendemos usar un árbol binario cuyas hojas contengan números, pero cuyos nodos no contengan operadores que presentan caracteres .La figura muestra este tipo de árbol binario.
Página 7
ESTRUCTURA DE DATOS
ITP
+ * 12
/ 3 4
1
Operaciones básicas con arboles binarios
•
Una tarea muy común a realizar con un árbol es ejecutar una determinada operación con cada uno de los elementos del árbol. Esta operación se considera entonces como un parámetro de una tarea más general que es la visita de todos los nodos o, como se denomina usualmente, del recorrido del árbol.
•
Puede haber muchas tareas a realizar con una estructura de árbol; una de corriente es ejecutar una operación P con cada uno de los elementos del árbol. P se considera entonces como un parámetro de una tarea mas general que es la visita a los nodos o, como se denomina usualmente, del recorrido del árbol.
•
Se aplican varias operaciones primitivas a n árbol binario. Si p es un apuntador a un nodo de un árbol binario, la función info(p) retorna el contenido de nodo. Las funciones left(p), rigth(p), father(p), brother(p); retornan apuntadores al hijo izquierdo de nodo , al hijo derecho de nodo , al padre de nodo y así respectivamente. Estas funciones retornan al apuntador null si no tiene padre, hijo izquierdo, hijo derecho, o hermano.
Si se considera la tarea como un proceso secuencial, entonces los nodos individuales se visitan en un orden específico, y pueden considerarse como organizados según una estructura lineal. De hecho, se simplifica considerablemente la descripción de muchos algoritmos si puede hablarse del proceso del siguiente elemento en el árbol, según un cierto orden subyacente. Hay dos formas básicas de recorrer un árbol: El recorrido en amplitud y el recorrido en profundidad.
PROFUNDIDAD
Página 8
ESTRUCTURA DE DATOS
ITP
La profundidad de un árbol binario es una característica que se necesita conocer con frecuencia durante el desarrollo de una aplicación con árboles. La función Profundidad evalúa la profundidad de un árbol binario. Para ello tiene un parámetro que es un puntero a la raíz del árbol. El desarrollo de una aplicación con árboles. La función Profundidad evalúa la profundidad de un árbol binario. Para ello tiene un parámetro que es un puntero a la raíz del árbol. El caso más sencillo de cálculo de la profundidad es cuando el árbol está vacío en cuyo caso la profundidad es O. Si el árbol no está vacío, cada subárbol debe tener su propia profundidad, por lo que se necesita evaluar cada una por separado. Las variables profundidad1, profundidad almacenarán las profundidades de los sub árboles izquierdo y derecho respectivamente. El método de cálculo de la profundidad de los sub árboles utiliza llamadas recursivas a la función Profundidad con punteros a los respectivos sub árboles como parámetros de la misma. La función Profundidad devuelve como resultado la profundidad del subárbol mas profundo más I (la misma de la raíz). int Profundidad (Nodo *p) { if (!p) else return O ; { int profundidad1 = Profundidad (p -> hijo-izqdo.); int profundidad2 = Profundidad (p -> 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<25 Arbol[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
•
HIJO DERECHO
SEGUNDO PASO
GG
CUARTO PASO
TERCER PASO
MINIMO DE UN ARBOL POR MONTON La raíz será menor que los dos hijos.
Página 30
ESTRUCTURA DE DATOS •
RAIZ
•
RAIZ
ITP
SEGUNDO PASO
ULTIMO PASO
Códigos
Árbol binario #include <stdio.h> #include <stdlib.h> #include
Página 31
ESTRUCTURA DE DATOS
ITP
void eliminar (Nodo** r, int mat); void visualizar (Nodo* r); int main() { int nm; char nom[30] ; Nodo* R = O; / * Crea el árbol * / do { printf ("Numero de matricula (O -> Fin) : " ) ; scanf ("%d%*c", &nm) ; if (nm) { printf ("Nombre: " ) ; gets (nom) ; insertar(&R,nm,nom); } / * Opciones de escribir el árbol o borrar una registro * / }while (nmj; clrscr ( ) ; do { puts(" 1. Mostrar el árboi\n"); puts(“2. Eliminar un registro\n"); do scanf("%d%*c", &nm); while(nm
Página 32
ESTRUCTURA DE DATOS
ITP
Nodo * t ; t = (Nodo") malloc(sizeof(Nodo)); t -> nummat = id; strcpy(t->nombre,n); t -> 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<=nodos;i++){ dato=Integer.parseInt( JOptionPane.showInputDialog(null,"ingrese el dato a insertar en el arbol") ); arbol.insertarNodo(dato); } }//end construye if(e.getSource()==pre){ JOptionPane.showMessageDialog(null,"Preorden : "+arbol.preorden()); }//end preorden if(e.getSource()==inor){ JOptionPane.showMessageDialog(null,"Inorden : "+arbol.inorden()); }//end inorden if(e.getSource()==pos){ JOptionPane.showMessageDialog(null,"Posorden : "+arbol.posorden()); }//end posorden if(e.getSource()==alt){ JOptionPane.showMessageDialog(null,"Altura : "+arbol.altura(arbol.retornaraiz())); }//end altura if(e.getSource()==hoj){ JOptionPane.showMessageDialog(null,"Hojas : "+arbol.hojas(arbol.retornaraiz())); }//end hojas if(e.getSource()==anc){ int db=Integer.parseInt(JOptionPane.showInputDialog(null,"Ingrese el dato cuyos ancestros desea conocer")); JOptionPane.showMessageDialog(null,"Ancestro : "+arbol.ancestros(arbol.retornaraiz(),db)); }//end ancestros if(e.getSource()==mostrar){ mostrarArbol(arbol.retornaraiz(),aux); c.removeAll(); c.add(most); c.setBackground(Color.WHITE); c.repaint();
Página 37
ESTRUCTURA DE DATOS
ITP
}//end mostrar if(e.getSource()==nuevo){ c.removeAll(); arbol=new Arbol(); cadena=new String(); most=new TextArea(); dato=0;nodos=0; aux="R";fila=" ";columna=" "; c.setBackground(Color.WHITE); }//end nuevo if(e.getSource()==creditos){ c.removeAll(); JLabel cred=new JLabel("ESTE PROGRAMA FUE DISEÑADO POR JUAN RICARDO COGOLLO OYOLA"); cred.setBounds(###TELEFONO_CENSURADO###); cred.setFont(new Font("EuropeExt", Font.BOLD + Font.ITALIC, 14)); cred.setForeground(Color.DARK_GRAY); c.setBackground(Color.white); c.add(cred); c.repaint(); }
if(e.getSource()==salir){ System.exit(0); }//end salir
}}
public static void main(String[] args) { PruebaArbol ventana = new PruebaArbol("ARBOLES BINARIOS DE BUSQUEDA"); ventana.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); }
Página 38
ESTRUCTURA DE DATOS
ITP
void pintar(int d,String h){ cadena=cadena+columna+fila+h+" : "+String.valueOf(d); most = new TextArea("",200,300,0); most.setBounds(###TELEFONO_CENSURADO###); most.append(cadena); most.setEditable(false); } void mostrarArbol(NodoArbol R,String hijo){ String h=hijo; if(R!=null){ pintar(R.retornadato(),h);
if(R.li!=null){ aux="Izq"; fila=fila+" "; mostrarArbol(R.li,aux); int n=fila.length(); fila=fila.substring(10); } if(R.ld!=null){ aux="Der"; fila=fila+" "; mostrarArbol(R.ld,aux); int n=fila.length(); fila=fila.substring(10); } } }//end windows
}
Árbol en montón Página 39
ESTRUCTURA DE DATOS
ITP
#include
Página 40
ESTRUCTURA DE DATOS
ITP
} cout<<"Arbol Lleno..."<<endl; } void Eliminar(int a) { int t; if(N!=0) { OrdMon(N); for(int i=0;i
Página 41
ESTRUCTURA DE DATOS
ITP
return; } } } cout<<"Arbol Vacio... Imposible Eliminar..."<<endl; } void Busqueda(int a) { if(N!=0) { OrdMon(N); for(int i=0;i
Página 42
ESTRUCTURA DE DATOS
ITP
void OrdMon(int n) { ConstMon(n); while(n>1) { n--; Burbuja(0,n); RecMon(n,0); } } void ConstMon(int n) { for(int v=n/2-1;v>=0;v--) RecMon(n,v); } void RecMon(int n,int v) { int w=2*v+1; while(w
Página 43
ESTRUCTURA DE DATOS
ITP
if (Arbol[w+1]>Arbol[w]) w++; if(Arbol[v]>=Arbol[w]) return; Burbuja(v,w); v=w; w=2*v+1; } } void Burbuja(int i,int j) { int t=Arbol[i]; Arbol[i]=Arbol[j]; Arbol[j]=t; } void Recorrido() { if(N!=0) { for(int i=0;i
Página 44
ESTRUCTURA DE DATOS
ITP
} cout<<"Arbol Vacio..."<<endl; } }tec; main() { int res,op=0; while(op!=5) { clrscr(); cout<<"\n1) Recorrido\n2) Busqueda\n3) Insercion\n4) Eliminar\n5) Salir"<<endl; gotoxy(1,1); cout<<"Que deseas hacer?: "; cin rel="nofollow">>op; gotoxy(1,10); switch (op) { case 1: tec.Recorrido(); break; case 2:
Página 45
ESTRUCTURA DE DATOS
ITP
cout<<"Que Numero deseas buscar?"<<endl; cin>>res; tec.Busqueda(res); break; case 3: cout<<"Que Numero quieres Insertar?"<<endl; cin>>res; tec.Insertar(res); break; case 4: cout<<"Que Numero quieres Eliminar?"<<endl; cin>>res; tec.Eliminar(res); break; case 5: cout<<"Salida..."; break; default: cout<<"Opcion Erronea"<<endl; break; } getch();
Página 46
ESTRUCTURA DE DATOS
ITP
} }
Página 47
