Capítulo 13: Estructura de datos no lineales (árboles y grafos) PDF

CAPÍTULO 13 Estructura de datos no lineales (árboles y grafos) 13.1. Introducción ACTIVIDADES DE PROGRAMACIÓN RESUELTAS 13.2. Árboles CONCEPTOS...

CAPÍTULO 13 Estructura de datos no lineales (árboles y grafos) 13.1. Introducción ACTIVIDADES DE PROGRAMACIÓN RESUELTAS 13.2. Árboles CONCEPTOS CLAVE 13.3. Árbol binario RESUMEN 13.4. Árbol binario de búsqueda EJERCICIOS 13.5. Grafos INTRODUCCIÓN Las estructuras dinámicas lineales de datos —listas tarán las estructuras de datos no lineales que resuel- enlazadas, pilas y colas— tienen grandes ventajas de ven los problemas que plantean las listas lineales y en flexibilidad sobre las representaciones contiguas; sin las que cada elemento puede tener diferentes “si- embargo, tienen un punto débil: son listas secuencia- guientes” elementos, que introducen el concepto de les, es decir, están dispuestas de modo que es nece- estructuras de bifurcación. Estos tipos de datos se lla- sario moverse a través de ellas una posición cada vez man árboles. (cada elemento tiene un siguiente elemento). Esta li- Asimismo, este capítulo introduce a una estructura nealidad es típica de cadenas, de elementos que per- matemática importante que tiene aplicaciones en tenecen a una sola dimensión: campos en un registro, ciencias tan diversas como la sociología, química, físi- entradas en una pila, entradas en una cola y de nodos ca, geografía y electrónica. Estas estructuras se deno- en una lista enlazada simple. En este capítulo se tra- minan grafos. 480 Fundamentos de programación 13.1. INTRODUCCIÓN Las estructuras de datos que han sido examinadas hasta ahora en este libro son lineales. A cada elemento le corres- pondía siempre un “siguiente” elemento. La linealidad es típica de cadenas, de elementos de arrays o listas, de cam- pos en registros, entradas en pilas o colas y nodos en listas enlazadas. En este capítulo se examinarán las estructuras de datos no lineales. En estas estructuras cada elemento puede tener diferentes “siguientes” elementos, que introduce el concepto de estructuras de bifurcación. Las estructuras de datos no lineales son árboles y grafos. A estas estructuras se les denomina también estructuras multienlazadas. 13.2. ÁRBOLES El árbol es una estructura de datos fundamental en informática, muy utilizada en todos sus campos, porque se adap- ta a la representación natural de informaciones homogéneas organizadas y de una gran comodidad y rapidez de ma- nipulación. Esta estructura se encuentra en todos los dominios (campos) de la informática, desde la pura algorítmica (métodos de clasificación y búsqueda...) a la compilación (árboles sintácticos para representar las expresiones o pro- ducciones posibles de un lenguaje) o incluso los dominios de la inteligencia artificial (árboles de juegos, árboles de decisiones, de resolución, etc.). Las estructuras tipo árbol se usan principalmente para representar datos con una relación jerárquica entre sus elementos, como son árboles genealógicos, tablas, etc. Un árbol A es un conjunto finito de uno o más nodos, tales que: 1. Existe un nodo especial denominado RAIZ(v1) del árbol. 2. Los nodos restantes (v2, v3,..., vn) se dividen en m >= 0 conjuntos disjuntos denominado A1, A2,..., Am, cada uno de los cuales es, a su vez, un árbol. Estos árboles se llaman subárboles del RAIZ. La definición de árbol implica una estructura recursiva. Esto es, la definición del árbol se refiere a otros árboles. Un árbol con ningún nodo es un árbol nulo; no tiene raíz. La Figura 13.1 muestra un árbol en el que se ha rotulado cada nodo con una letra dentro de un círculo. Esta es una notación típica para dibujar árboles. Los tres subárboles del raíz A son B, C y D, respectivamente. B es la raíz de un árbol con un subárbol E. Este subárbol no tiene subárbol conectado. El árbol C tiene dos subárboles, F y G. + log ! a b x n – o a * < < b c a b c d Figura 13.1. Diferentes árboles.  Estructura de datos no lineales (árboles y grafos) 481 13.2.1. Terminología y representación de un árbol general La representación y terminología de los árboles se realiza con las típicas notaciones de las relaciones familiares en los árboles genealógicos: padre, hijo, hermano, ascendente, descendiente, etc. Sea el árbol general de la Figu- ra 13.2. A B C D E F G H I J K L Figura 13.2. Árbol general. Las definiciones a tener en cuenta son: Raíz del árbol. Todos los árboles que no están vacíos tienen un único nodo raíz. Todos los demás elementos o nodos se derivan o descienden de él. El nodo raíz no tiene padre, es decir, no es el hijo de ningún elemento. Nodo, son los vértices o elementos del árbol. Nodo terminal u hoja (leaf node) es aquel nodo que no contiene ningún subárbol (los nodos terminales u hojas del árbol de la Figura 13.2 son E, F, K, L, H y J). A cada nodo que no es hoja se asocia uno o varios subárboles llamados descendientes (offspring) o hijos. De igual forma, cada nodo tiene asociado un antecesor o ascendiente llamado padre. Los nodos de un mismo padre se llaman hermanos. Los nodos con uno o dos subárboles —no son hojas ni raíz— se llaman nodos interiores o internos. Una colección de dos o más árboles se llama bosque (forest). Todos los nodos tienen un solo padre —excepto el raíz— que no tiene padre. Se denomina camino el enlace entre dos nodos consecutivos y rama es un camino que termina en una hoja. Cada nodo tiene asociado un número de nivel que se determina por la longitud del camino desde el raíz al nodo específico. Por ejemplo, en el árbol de la Figura 13.2. Nivel 0 A Nivel 1 B, C, D Nivel 2 E, F, G, H, I, J Nivel 3 K, L La altura o profundidad de un árbol es el número máximo de nodos de una rama. Equivale al nivel más alto de los nodos más uno. El peso de un árbol es el número de nodos terminales. La altura y el peso del árbol de la Figura 13.2 son 4 y 7, respectivamente. Las representaciones gráficas de los árboles —además de las ya expuestas— pueden ser las mostradas en la Fi- gura 13.3. 482 Fundamentos de programación A B C D E F G H I J K L E D H J B I A F G K C L Figura 13.3 Representaciones de árboles. 13.3. ÁRBOL BINARIO Existe un tipo de árbol denominado árbol binario que puede ser implementado fácilmente en una computadora. Un árbol binario es un conjunto finito de cero o más nodos, tales que: Existe un nodo denominado raíz del árbol. Cada nodo puede tener 0, 1 o 2 subárboles, conocidos como subárbol izquierdo y subárbol derecho. La Figura 13.4 representa diferentes tipos de árboles binarios: (a) T (b) T1 (c) T2 + A / 5 100 B C 100 5 Figura 13.4. Ejemplos de árboles binarios: (a) expresión árbol a + b/c; (b) y (c) dos árboles diferentes con valores enteros.  Estructura de datos no lineales (árboles y grafos) 483 13.3.1. Terminología de los árboles binarios Dos árboles binarios se dice que son similares si tienen la misma estructura, y son equivalentes si son similares y contienen la misma información (Figura 13.5). Un árbol binario está equilibrado si las alturas de los dos subárboles de cada nodo del árbol se diferencian en una unidad como máximo. altura (subárbol izquierdo) – altura (subárbol derecho) ≤ 1 A A B C X T C E C G F Q (a) (b) Figura. 13.5. Árboles binarios: (a) similares, (b) equivalentes. El procesamiento de árboles binarios equilibrados es más sencillo que los árboles no equilibrados. En la Figu- ra 13.6 se muestran dos árboles binarios de diferentes alturas y en la Figura 13.7, árboles equilibrados y sin equi- librar. T T1 T2 F / E – –22 D C 14 7 B A (a) (b) (c) Figura 13.6. Árboles binarios de diferentes alturas: (a) altura 3, (b) árbol vacío, altura 0, (c) altura 6. 484 Fundamentos de programación a 5 b d 4 2 e g h i 3 1 1 f j 2 1 (a) (b) Figura 13.7. Arboles binarios: (a) equilibrados, (b) no equilibrados. 13.3.2. Árboles binarios completos Un árbol binario se llama completo si todos sus nodos tienen exactamente dos subárboles, excepto los nodos de los niveles más bajos que tienen cero. Un árbol binario completo, tal que todos los niveles están llenos, se llama árbol binario lleno. En la Figura 13.8 se ilustran ambos tipos de árboles. Un árbol binario T de nivel h puede tener como máximo 2h – 1 nodos. La altura de un árbol binario lleno de n nodos es log2(n + 1). A la inversa, el número máximo de nodos de un árbol binario de altura h será 2h – 1. En la Figura 13.9 se muestra la relación matemática que liga los nodos de un árbol. Por último, se denomina árbol degenerado un árbol en el que todos sus nodos tienen solamente un subárbol, excepto el último. T T H D D L B E B F J N A C A C E G I K M O (a) (b) Figura 13.8. (a) árbol binario lleno de altura 4, (b) árbol binario completo de altura 3.  Estructura de datos no lineales (árboles y grafos) 485 T Altura (H) = 3 Número de nodos (N) = 7 = 2h – 1 Nivel 3; número de nodos = 2(3–1) = 4 D B F A C E G Figura 13.9. Relaciones matemáticas de un árbol binario. 13.3.3. Conversión de un árbol general en árbol binario Dado que los árboles binarios es la estructura fundamental en la teoría de árboles, será preciso disponer de algún mecanismo que permita la conversión de un árbol general en un árbol binario. Los árboles binarios son más fáciles de programar que los árboles generales. En éstos es imprescindible deducir cuántas ramas o caminos se desprenden de un nodo en un momento dado. Por ello, y dado que de los árboles binarios siempre se cuelgan como máximo dos subárboles, su programación será más sencilla. Afortunadamente existe una técnica para convertir un árbol general a formato de árbol binario. Supongamos que se tiene el árbol A y se quiere convertir en un árbol binario B. El algoritmo de conversión tiene tres pasos fáciles: 1. La raíz de B es la raíz de A. 2. a) Enlazar al nodo raíz con el camino que conecta el nodo más a la izquierda (su hijo). b) Enlazar este nodo con los restantes descendientes del nodo raíz en un camino, con lo que se forma el nivel 1. c) A continuación, repetir los pasos a) y b) con los nodos del nivel 2, enlazando siempre en un mismo ca- mino todos los hermanos —descendientes del mismo nodo—. Repetir estos pasos hasta llegar al nivel más alto. 3. Girar el diagrama resultante 45° para diferenciar entre los subárboles izquierdo y derecho. T T A A B B C C D D E E Figura 13.10. Árboles degenerados. 486 Fundamentos de programación EJEMPLO 13.1 Convertir el árbol general T en un árbol binario. A B C D E F G H I J K L Siguiendo los pasos del algoritmo. Paso 1: A B C D E F G H I J K L Paso 2: A B E C F D G H K I L J  Estructura de datos no lineales (árboles y grafos) 487 Paso 3: Obsérvese que no existe camino entre E y F, debido a que no son descendientes del árbol original, ya que ellos tienen diferentes padres B y C. En el árbol binario resultante los punteros izquierdos son siempre de un nodo padre a su primer hijo (más a la izquierda) en el árbol general original. Los punteros derechos son siempre desde un nodo de sus descendientes en el árbol original. EJEMPLO 13.2 El algoritmo de conversión puede ser utilizado para convertir un bosque de árboles generales a un solo árbol bi- nario. El bosque siguiente puede ser representado por un árbol binario. Bosque de árboles: A C I J B D K L E F G M N O P H Árbol binario equivalente A B C D I E J F K H G L M N O P 488 Fundamentos de programación EJEMPLO 13.3 Convertir el árbol general en árbol binario. a b c d e g h i f j Solución Paso 1: a b Paso 2: a b c d e g h i f j Paso 3: a b c e d f g h i J  Estructura de datos no lineales (árboles y grafos) 489 13.3.4. Representación de los árboles binarios Los árboles binarios pueden ser representados de dos modos diferentes: Mediante punteros (lenguajes C y C++). Mediante arrays o listas enlazadas. Vinculando nodos, objetos con mienbros que referencian otros objetos del mismo tipo. 13.3.4.1. 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 del subárbol izquierdo (que puede ser nulo-null). Un puntero al nodo del subárbol derecho (que puede ser nulo-null). CLAVE CLAVE CLAVE NULO Figura 13.11. Representación de un árbol con punteros. Ramón Josefina Andrés Miguel Laura Ana Pascal Manuel Erika Koldo Clemente En lenguaje algorítmico se tendrá: tipo nodo_arbol puntero_a nodo_arbol: punt registro : nodo_arbol 490 Fundamentos de programación : elemento punt: subiz, subder fin_registro 13.3.4.2. Representación por listas enlazadas Mediante una lista enlazada se puede siempre representar el árbol binario de la Figura 13.12. A B C D E F G Figura 13.12. Árbol binario. Nodo del árbol: campo 1 INFO (nodo) campo 2 IZQ (nodo) campo 3 DER (nodo) El árbol binario representado como una lista enlazada se representa en la Figura 13.13. IZDA INFO DCHA A B NULO C NULO D NULO NULO E NULO F NULO NULO G NULO Figura 13.13. Árbol binario como lista enlazada. 13.3.4.3. Representación por arrays Existen diferentes métodos; uno de los más fáciles es mediante tres arrays lineales paralelos que contemplan el cam- po de información y los dos punteros de ambos subárboles. Así, por ejemplo, el nodo raíz RAMÓN tendrá dos punteros  Estructura de datos no lineales (árboles y grafos) 491 IZQ:(9) —JOSEFINA— y DER:(16) —ANDRÉS—, mientras que el nodo CLEMENTE, al no tener descendientes, sus punteros se consideran cero (IZQ:0, DER:0). 3 Ramón 9 Josefina Andrés 16 6 Miguel 7 Laura 15 Ana 4 Pascal 12 Manuel 11 Erika 8 Koldo 13 Clemente 16 ANDRÉS 15 4 15 ANA 8 0 14 13 CLEMENTE 0 0 12 MANUEL 0 0 11 ERIKA 0 0 10 9 JOSEFINA 6 7 8 KOLDO 0 0 7 LAURA 11 0 6 MIGUEL 12 0 5 4 PASCAL 0 13 3 RAMÓN 9 16 P 2 1 INFO IZQ. DER. Figura 13.14. Árbol binario como arrays. Otro método resulta más sencillo —un array lineal—. Para ello se selecciona un array lineal ARBOL. 50 21 75 12 32 90 16 25 85 492 Fundamentos de programación El algoritmo de transformación es: 1. La raíz del árbol se guarda en ARBOL. 2. si un nodo n está en ARBOL[i] entonces su hijo izquierdo se pone en ARBOL[2*i] y su hijo derecho en ARBOL[2*i + 1] si un subárbol está vacío, se le da el valor NULO. Este sistema requiere más posiciones de memoria que nodos tiene el árbol. Así, la transformación necesitará un array con 2h + 2 elementos si el árbol tiene una profundidad h. En nuestro caso, como la profundidad es 3, requerirá 32 posiciones (25), aunque si no se incluyen las entradas nulas de los nodos terminales, veremos cómo sólo necesita catorce posiciones. Árbol 1 50 2 21 3 75 4 12 5 32 6 0 7 90 8 0 9 16 10 25 11 12 13 14 85 15 16 17 18...  Estructura de datos no lineales (árboles y grafos) 493 Un tercer método, muy similar al primero, sería la representación mediante un array de registros. INFO IZQ DER P 3 1 2 3 RAMÓN 9 16 4 PASCAL 0 13 5 6 MIGUEL 12 0 7 LAURA 11 0 8 KOLDO 0 0 9 JOSEFINA 6 7 10 11 ERIKA 0 0 12 MANUEL 0 0 13 CLEMENTE 0 0 14 15 ANA 8 0 16 ANDRÉS 15 4 13.3.5. Recorrido de un árbol binario Se denomina recorrido de un árbol el proceso que permite acceder una sola vez a cada uno de los nodos del árbol. Cuando un árbol se recorre, el conjunto completo de nodos se examina. Existen muchos modos para recorrer un árbol binario. Por ejemplo, existen seis diferentes recorridos generales en profundidad de un árbol binario, simétricos dos a dos. Los algoritmos de recorrido de un árbol binario presentan tres tipos de actividades comunes: Visitar el nodo raíz. Recorrer el subárbol izquierdo. Recorrer el subárbol derecho. Estas tres acciones repartidas en diferentes órdenes proporcionan los diferentes recorridos del árbol en profundi- dad. Los más frecuentes tienen siempre en común recorrer primero el subárbol izquierdo y luego el subárbol derecho. Los algoritmos que lo realizan llaman pre-orden, post-orden, in-orden y su nombre refleja el momento en que se visita el nodo raíz. En el in-orden el raíz está en el medio del recorrido, en el pre-orden el raíz está el primero y en el post-orden el raíz está el último: Recorrido pre-orden 1. Visitar el raíz. 2. Recorrer el subárbol izquierdo en pre-orden. 3. Recorrer el subárbol derecho en pre-orden. Recorrido in-orden 1. Recorrer el subárbol izquierdo en in-orden. 2. Visitar el raíz. 3. Recorrer el subárbol derecho en in-orden. 494 Fundamentos de programación Recorrido post-orden 1. Recorrer el subárbol izquierdo en post-orden. 2. Recorrer el subárbol derecho en post-orden. 3. Visitar el raíz. Obsérvese que todas estas definiciones tienen naturaleza recursiva. En la Figura 13.15 se muestran los recorridos de diferentes árboles binarios. + / M * e + g E P d ↑ B L N V c * Árbol 1: c * d + e + / e f A D T Z Árbol 3 a b c d Árbol 2: [((a + b) * c/d) + e ^ f]/g Figura 13.15. Recorrido de árboles binarios. Árbol 1 Pre-orden + * c d e In-orden c * d + e Post-orden c d * e + Árbol 2 Pre-orden / + * + a b / c d ^ e f g In-orden a + b * c / d + e ^ f / g Post-orden a b + c d / * e f ^ + g / Árbol 3 Pre-orden MEBADLPNVTZ In-orden ABDELMNPTVZ Post-orden ADBLENTZVPM EJEMPLO 13.4 Calcular los recorridos del árbol binario. (/) * e + (–) a b c d Solución recorrido pre-orden / * + ab - cde recorrido in-orden a + b * c - d/e recorrido post-orden ab + cd - * e/  Estructura de datos no lineales (árboles y grafos) 495 EJEMPLO 13.5 Realizar los recorridos del árbol binario. 2 5 8 1 4 10 7 12 Solución recorrido pre-orden 2 5 1 7 4 8 10 12 recorrido in-orden 1 7 5 4 2 8 12 10 recorrido post-orden 7 1 4 5 12 10 8 2 13.4. ÁRBOL BINARIO DE BÚSQUEDA Recordará del Capítulo 10, “Ordenación, búsqueda e intercalación”, que para localizar un elemento en un array se podía realizar una búsqueda lineal; sin embargo, si el array era grande, una búsqueda lineal era ineficaz por su len- titud, especialmente si el elemento no estaba en el array, ya que requería la lectura completa del array. Se ganaba tiempo si se clasificaba el array y se utilizaba una búsqueda binaria. Sin embargo, en un proceso de arrays las inser- ciones y eliminaciones son continuas, por lo que esto se hará complejo en cualquier método. En los casos de gran número de operaciones sobre arrays o listas, lo que se necesita es una estructura donde los elementos puedan ser eficazmente localizados, insertados o borrados. Una solución a este problema es una varian- te del árbol binario que se conoce como árbol binario de búsqueda o árbol binario clasificado (binary search tree). El árbol binario de búsqueda se construirá teniendo en cuenta las siguientes premisas: El primer elemento se utiliza para crear el nodo raíz. Los valores del árbol deben ser tales que pueda existir un orden (entero, real, lógico o carácter e incluso defi- nido por el usuario si implica un orden). En cualquier nodo todos los valores del subárbol izquierdo del nodo son menor o igual al valor del nodo. De modo similar, todos los valores del subárbol derecho deben ser mayores que los valores del nodo. Si estas condiciones se mantienen, es sencillo probar que el recorrido in-orden del árbol produce los valores clasificados por orden. Así, por ejemplo, en la Figura 13.16 se muestra un árbol binario. Los tres recorridos del árbol son: pre-orden P F B H G S R Y T W Z in-orden B F G H P R S T Y W Z post-orden B G H F R T W Z Y S P En esencia, un árbol binario contiene una clave en cada nodo que satisface las tres condiciones anteriores. Un árbol con las propiedades anteriores se denomina árbol binario de búsqueda. 496 Fundamentos de programación P F S B H H Y G T T W Figura 13.16. Árbol binario. EJEMPLO 13.6 Se dispone de un array que contiene los siguientes caracteres: D F E B A C G Construir un árbol binario de búsqueda. Los pasos para la construcción del algoritmo son: 1. Nodo raíz del árbol: D. 2. El siguiente elemento se convierte en el descendente derecho, dado que F alfabéticamente es mayor que D. 3. A continuación, se compara E con el raíz. Dado que E es mayor que D, pasará a ser un hijo de F y como E < F será el hijo izquierdo. 4. El siguiente elemento B se compara con el raíz D y como B < D y es el primer elemento que cumple esta condición, B será el hijo izquierdo de D. 5. Se repiten los pasos hasta el último elemento. El árbol binario de búsqueda resultante sería: D B F A C E G EJEMPLO 13.7 Construir el árbol binario de búsqueda correspondiente a la lista de números. 4 19 -7 49 100 0 22 12  Estructura de datos no lineales (árboles y grafos) 497 El primer valor, como ya se ha comentado, es la raíz del árbol: es decir, 4. El siguiente valor, 19, se compara con 4; como es más grande se lleva al subárbol derecho de 4. El siguiente valor, –7, se compara con el raíz y es menor que su valor, 4; por tanto, se mueve al subárbol izquierdo. La Figura 13.17 muestra los sucesivos pasos. 4 –7 19 0 12 49 22 100 Figura 13.17. Construcción de un árbol binario. 13.4.1. Búsqueda de un elemento La búsqueda en un árbol binario ordenado es dicotómica, ya que a cada examen de un nodo se elimina aquel de los subárboles que no contiene el valor buscado (valores todos inferiores o todos superiores). 13 9 45 5 11 50 7 10 12 48 52 El algoritmo de búsqueda del elemento —clave x— se realiza comparándolo con la clave del raíz del árbol. Si no es el mismo, se pasa al subárbol izquierdo o derecho, según el resultado de la comparación, y se repite la búsque- da en ese subárbol. La terminación del procedimiento se producirá cuando: Se encuentra la clave. No se encuentra la clave; se continúa hasta encontrar un subárbol vacío. procedimiento buscar (E punt: RAIZ; E : elemento; S punt: actual, anterior) var logico: encontrado inicio encontrado ← falso anterior ← nulo actual ← raiz mientras no encontrado Y (actualnulo) hacer si actual→.elemento = elemento entonces 498 Fundamentos de programación encontrado ← verdad si_no anterior ← actual si actual→.elemento > elemento entonces actual ← actual→.izdo si_no actual ← actual→.dcho fin_si fin_si fin_mientras si no encontrado entonces escribir('no existe', elemento) si_no escribir( elemento, 'existe') fin_si fin_procedimiento //< tipo_elemento> en este algoritmo es un tipo de dato simple 13.4.2. Insertar un elemento Para insertar un elemento en el árbol A se ha de comprobar, en primer lugar, que el elemento no se encuentra en el árbol, ya que su caso no precisa ser insertado. Si el elemento no existe, la inserción se realiza en un nodo en el que al menos uno de los dos punteros izq o der tenga valor nulo. Para realizar la condición anterior se desciende en el árbol a partir del nodo raíz, dirigiéndose de izquierda a de- recha de un nodo, según que el valor a insertar sea inferior o superior al valor del campo clave INFO de este nodo. Cuando se alcanza un nodo del árbol en que no se puede continuar, el nuevo elemento se engancha a la izquierda o derecha de este nodo en función de que su valor sea inferior o superior al del nodo alcanzado. El algoritmo de inserción del elemento x es: procedimiento insertar (E/S punt: raiz; E : elemento) var punt : nuevo, actual, anterior inicio buscar (raiz, elemento, actual, anterior) si actual NULO entonces escribir ('elemento duplicado') si_no reservar (nuevo) nuevo→.elemento ← elemento nuevo→.izdo ← nulo nuevo→.dcho ← nulo si anterior = nulo entonces raiz ← nuevo si_no si anterior→.elemento > elemento entonces anterior→.izdo ← nuevo si_no anterior→.dcho ← nuevo fin_si fin_si fin_si fin_procedimiento // es un tipo simple  Estructura de datos no lineales (árboles y grafos) 499 T T T 4 4 4 –7 19 –7 19 –7 19 49 0 49 0 12 49 100 100 22 100 (a) (b) (c) Figura 13.18. Inserciones en un árbol de búsqueda binaria: (a) insertar 100, (b) insertar (0), (c) insertar 22 y 12. Para insertar el valor x en el árbol binario ordenado se necesitará llamar al subprograma insertar. 13.4.3. Eliminación de un elemento La eliminación de un elemento debe conservar el orden de los elementos del árbol. Se consideran diferentes casos, según la posición del elemento o nodo en el árbol: Si el elemento es una hoja, se suprime simplemente. Si el elemento no tiene más que un descendiente, se sustituye entonces por ese descendiente. Si el elemento tiene dos descendientes, se sustituye por el elemento inmediato inferior situado lo más a la dere- cha posible de su subárbol izquierdo. Para poder realizar estas acciones será preciso conocer la siguiente información del nodo a eliminar: Conocer su posición en el árbol. Conocer la dirección de su padre. Conocer si el nodo a eliminar tiene hijos, si son 1 o 2 hijos, y en el caso de que sólo sea uno, si es hijo derecho o izquierdo. La Figura 13.19 muestra los tres posibles casos de eliminación de un nodo: (a) eliminar C, (b) eliminar F, (c) eliminar B. T T T B B D A \ A F B E C D A C C E (a) (b) (c) Figura 13.19. Casos posibles de eliminación de un nodo. 500 Fundamentos de programación En la Figura 13.20 se muestra el caso de eliminación de un nodo con un subárbol en un gráfico comparativo antes y después de la eliminación. T T 4 4 –7 19 N –7 19 49 100 100 (a) (b) Figura 13.20. Eliminación de un nodo con un subárbol. En la Figura 13.21 se muestra el caso de la eliminación de un nodo (27) que tiene dos subárboles no nulos. En este caso se busca el nodo sucesor cuyo campo de información le siga en orden ascendente, es decir, 42, se intercam- bia entonces con el elemento que se desea borrar, 27. T T 4 4 –7 27 N –7 42 –9 22 49 –9 22 49 12 42 100 12 100 (a) (b) Figura 13.21. Eliminación de un nodo con dos subárboles no nulos. EJEMPLO 13.8 Deducir los árboles resultantes de eliminar el elemento 3 en el árbol A y el elemento 7 en el árbol B. Árbol A 8 8 3 9 4 9 2 5 11 2 5 11 4 6 10 19 6 10 19 17 17  Estructura de datos no lineales (árboles y grafos) 501 Árbol B. En este caso se busca el nodo sucesor cuyo campo de información le siga en orden decreciente, es decir, 6. 16 16 7 18 6 18 4 9 24 4 9 24 2 6 8 10 2 8 10 Árbol binario mediante arrays Los árboles deben ser tratados como estructuras dinámicas. No obstante, si el lenguaje no tiene punteros podremos simularlos mediante arrays. ELEMENTO IZQ DER XXXX N.o N. o RAÍZ N.o VACÍ O N.o Izdo y dcho serán dos campos numéricos para indicar la posición en que están los hijos izquierdo y derecho. El valor 0 indicaría que no tiene hijo. Trataremos el array como una lista ENLAZADA y necesitaremos una LISTA DE VACIOS y una variable VACIO que apunte al primer elemento de la lista de vacíos. Para almacenar la lista de vacíos es indiferente que utilicemos el campo Izdo o Dcho. EJEMPLO 13.9 algoritmo arbol_binario_mediante_arrays const Max = tipo registro: TipoElemento... :...... :... fin_registro registro: TipoNodo TipoElemento : Elemento Entero : Izdo, Dcho fin_registro array[1..Max] de TipoNodo : Arr var Arr : a 502 Fundamentos de programación Entero : opcion TipoElemento : elemento Entero : raiz Entero : vacio inicio iniciar(a,raiz,vacio) repetir menu escribir ('OPCIÓN: ') repetir leer (opcion) hasta_que (opcion >= 0) Y (opcion