273690 Tema 05 Arboles Parte I

1

TEMA 5: Árboles (parte I)Trie, genéricos y binarios

Estructuras de Datos

Ingeniería Técnica Informática de Gestión

2

Contenido

Introducción y Definiciones. Un tipo especial de árbol: el árbol Trie

– Representación de Tries– Evaluación de Tries

El TAD Árbol– Representación hijo izquierdo-hermano derecho

Árboles binarios– El TAD Árbol binario

3

Introducción

Un árbol es una estructura de datos no lineal Se apoya sobre una relación binaria de orden NO necesariamente

total:– Es decir, existen elementos que no son comparables entre sí.

Ej: (N2,<), donde N={0,1,2,…,n,…} para todo X=(a,b), Y=(c,d) en N2, definimos la relación <, de tal forma que X<Y sii a < c.

Al representar gráficamente el retículo de esta relación observamos que los elementos YA NO se pueden disponer en una “línea” sino que forman una estructura más general, una estructura con ramificaciones.

Realmente las estructuras de datos lineales podrían verse comoun caso muy particular de las estructuras de datos árboreas.

– Informalmente, una estructura lineal sería un árbol sin ramificaciones.

4

Introducción

p

f a

ab

Estructura árbol: Almacenando en memoria la expresión lógica p( f(a, b), a).

Los árboles se aplican en múltiples campos de la informática:– ingeniería del conocimiento en I.A. (ej: espacio de búsqueda de una

partida del juego de las damas), árboles de decisión, representandoexpresiones lógicas (lenguajes de programación declarativos -PROLOG-), expresiones aritméticas, expresando ontologías (websemántica), en compilación de programas (árbol de derivacionessintácticas de un programa), etc.

5

Definiciones básicas

Árboles como grafos particulares:– Es un grafo no dirigido , acíclico y conexo.

Grafo ÁrbolBosque

Posee ciclos No conexo

6

Definiciones básicas: caracterización topológica de un árbol

Caracterización de un árbol: si G=(V,A) es un grafo no dirigido, las siguientes proposiciones son equivalentes:1. G es un árbol2. Cualquier par de vértices está conectado por un único camino3. G es conexo pero si se elimina cualquier arista de A, el grafo

es no conexo4. G es conexo y tiene |V|-1 aristas5. G es acíclico y tiene |V|-1 aristas6. G es acíclico, pero si se añade una arista se forma un ciclo.

7

Definiciones básicas: caracterización topológica de un árbol

Las propiedades topológicas de un árbol en particular y un grafoen general pueden ser utilizadas para demostrar propiedades yteoremas sobre estos objetos que a la postre se traducirán enalgoritmos de gran aplicabilidad. Además, las propiedades deestos objetos pueden ser explotadas también para optimizar laformulación del algoritmo (véase cualquier tratado sobre teoría degrafos).

Para demostrar la equivalencia de un conjunto de proposiciones,la estrategia a seguir suele ser demostrar la implicación porpares: (1) (2),…,(5) (6) y finalmente (6) (1). Así, decir queun grafo es un árbol es equivalente a decir que dicho grafo esconexo y posee |V|-1 aristas por ejemplo.

Cuestión: Justifique intuitivamente la equivalencia de lasproposiciones anteriores.

8


Nodo raíz: aunque el árbol sea un grafo no dirigido, interesa fijar un nodo especial (de partida) a partir del cual iniciar los recorridos sobre la estructura.

Si (x,y) es el último arco en el camino desde la raíz r de un árbol Thasta el nodo y, entonces

– El nodo x es padre del nodo y, y el nodo y es hijo del nodo x.– A los nodos con el mismo padre se les denomina nodos hermanos.– La raíz es el único nodo del árbol sin padre.

Los nodos de un árbol se clasifican en:– Internos: nodos con descendientes (con hijos)– Hojas: nodos sin descendientes (sin hijos)

9


El grado de un nodo es el número máximo de hijos que tiene. El grado de un árbol se corresponde con el máximo del grado de

sus nodos.– Árboles n-arios: árboles de grado n (máximo de n hijos por nodo)– Árboles binarios: árboles de grado 2 (máximo de 2 hijos por nodo)

La profundidad de un nodo es la longitud (nº de aristas) desde laráiz hasta el nodo.

La altura de un árbol es la profundidad del nodo más profundo(profundidad del árbol).

El nivel de un nodo es su profundidad+1.– Cuestión: ¿Cuál será el nivel del nodo raíz?

10

Definiciones básicas: caracterización computacional de un árbol

La estructura de datos árbol se puede definir recursivamente:– T es un árbol vacío si no tiene ningún nodo.– Si un grafo tiene un nodo, dicho grafo es un árbol y el nodo es el

nodo raíz.– Si T es un árbol con más de un nodo, entonces los descendientes de

T son a su vez nodos raíz de los subárboles que cuelgan de T. Es decir, al eliminar el nodo raíz de un árbol obtenemos un bosque de

árboles. Por lo tanto, un árbol es una estructura recursiva.

– Una estructura recursiva suele conducir a propiedades que se definen recursivamente.

– Aunque esto no signifique que la implementación de dichas propiedades sea recursiva. Si se puede, deberían ser iterativas.

11

Aplicación: representación de diccionarios (o en general conjuntos) grandes de palabras.

Ejemplo. Corrector ortográfico interactivo.

Árboles Trie

12

Diccionario español: ~ 3 millones de palabras. Muchas palabras Mucha memoria y operaciones

lentas. Pero la búsqueda de una palabra no puede tardar más

de 1 milisegundo...

... esparto esparvar esparvel esparver espasmar espasmo espasmódica espasmódico espata espatarrada espatarrarse

espática espático espato espátula espatulomancia espaviento espavorecida espavorecido espavorida espavorido espay

especería especia especial ...

Árboles Trie

13

Idea: muchas palabras tienen prefijos comunes. P. ej.: espasmar, espasmo, espasmódico, espasmódica, ...

Árboles Trie

14

Un Trie es, básicamente, un árbol de prefijos. Sea A un alfabeto. Por ejemplo A= {a, b, c, ..., z} Añadimos a A una marca de fin de palabra: $.

Definición: un Trie es una estructura de árbol en la que:1. La raíz del árbol representa la cadena vacía.2. Un nodo puede tener tantos hijos como caracteres del alfabeto

A más uno. Cada hijo está etiquetado con un carácter o una marca de fin $.

3. La sucesión de etiquetas desde la raíz hasta un nodo hoja, etiquetado con la marca de fin $, representa una palabra.

4. A todos los nodos, excepto a la raíz y a las hojas etiquetadas con $, se les denomina prefijos del árbol.

Árboles Trie

15

Ejemplo, C= {ELLA, ELLO, EL, TU, Y, YO} ¿Cómo usarlo en el corrector interactivo?

Árboles Trie

16

Se pueden representar otros tipos de información, cambiando el alfabeto A.

Ejemplo: representación de URL de páginas web.

Árboles Trie

17

Cuestión: ¿Cómo representar árboles trie?tipo

ArbolTrie[A]= Puntero[NodoTrie[A]]

Reformulamos la pregunta: ¿Cómo representar los nodos del árbol trie?

A C TN $

NodoTrie

Representación de tries

18

Un NodoTrie[A] es un Diccionario[tclave, tvalor], donde tclave= A y tvalor= Puntero[NodoTrie[A]]

Operaciones:

Inserta (var n: NodoTrie[A]; caract: A; ptr: Puntero[NodoTrie[A]])Consulta (n: NodoTrie[A]; caract: A): Puntero[NodoTrie[A]]Anula (var n: NodoTrie[A])TomaNuevo (var n: NodoTrie[A]; caract: A)


19

- Representación mediante arrays.

- Representación mediante listas.


20

- Representación mediante arrays.

tipoNodoTrie[A]= array [A] de Puntero[NodoTrie[A]]

• Ventaja: acceso muy rápido a los valores.• Inconveniente: desperdicia muy mucha memoria.


21

Inserta (var n: NodoTrie[A]; car: A; ptr: Puntero[NodoTrie[A]])n[car]:= ptr

Consulta (n: NodoTrie[A]; car: A): Puntero[NodoTrie[A]]devolver n[car]

Anula (var n: NodoTrie[A])para i en Rango(A) hacer

n[i]:= NULO

TomaNuevo (var n: NodoTrie[A]; car: A)n[car]:= NUEVO NodoTrie[A]Anula (n[car])


22

E T Y

$OUL

L $ $$

OA

$ $


Ejemplo, C= {ELLA, ELLO, EL, TU, Y, YO}

23



24

- Representación mediante listas.

tipo NodoTrie[A]= registrocar: Asig, ptr: Puntero[NodoTrie[A]]

finregistro

Ventaja: uso razonable de memoria. Inconveniente: operaciones más lentas.


25

Consulta (n: NodoTrie[A]; c: A): Puntero[NodoTrie[A]]tmp:= PunteroA(n)mientras tmp ≠ NULO AND tmpcar < c hacer

tmp:= tmpsigsi tmpcar ≠ c entonces devolver NULOsino devolver tmpptr

Inserta (var n: NodoTrie[A]; car: A; ptr: Puntero[NodoTrie[A]])1. Recorrer la lista buscando el carácter car2. Si se encuentra, modificar el puntero ptr3. En otro caso, añadir un nuevo nodo en la posición

adecuada, con el carácter car y el puntero ptr


26



27



28

Utilizando la representación de nodos trie (con listas o con arrays) implementar las operaciones de inserción, eliminación y consulta sobre el trie.

Ejemplo. Insertar ELLE. ET Y

$OUL

L $ $$

OA

$ $

E L L E $

iE

$

pos


29

operación Inserta (var a: ArbolTrie[A]; s: cadena)var pos: Puntero[NodoTrie[A]]

i:= 1pos:= amientras s[i] ≠ $ hacer

si Consulta (pos↑, s[i]) == NULO entoncesTomaNuevo (pos↑, s[i])

pos:= Consulta (pos↑, s[i])i:= i + 1

finmientrasInserta (pos↑, $, pos) // no confundir

Modificar el procedimiento para que haga una consulta. Si queremos añadir información asociada a cada palabra, ¿dónde

debería colocarse?


30

¿Cómo sería el uso del trie en el corrector interactivo?

Empezar una palabraColocar pos en la raíz del árbol

Pulsar una tecla c en una palabraSi Consulta (pos↑, c) == NULO entonces la palabra es incorrecta, en otro caso moverse en el árbol

Acabar una palabraSi Consulta (pos↑, $) == NULO entonces la palabra es incorrecta, en otro caso es correcta

Borrar una letra de una palabraMoverse hacia atrás en el árbol...


31

Tiempo de ejecución El principal factor en el tiempo de ejecución es la longitud

de las palabras: m. Nodos con arrays: O(m) Nodos con listas: O(m*s), donde s es la longitud promedio

de las listas. En la práctica, ~ O(m).

En el caso del corrector interactivo, la eficiencia es aún más interesante, pues no tenemos que recorrer las palabras enteras.

Evaluación de los tries

32

Uso de memoria Longitud promedio de las palabras: m. Longitud total: l Número de palabras: n. Número de prefijos: p k1 bytes/puntero, k2 bytes/carácter d caracteres en el alfabeto (incluido $) n << p << l

Nodos con arrays: d*k1 (p + 1) bytes – p+1 Nodos en el árbol– d*k1 bytes por nodo

Nodos con listas: (2k1 + k2)(n + p) bytes – n + p Nodos en el árbol– 2k1 + k2 bytes por nodo


33

Uso de memoria Con listas simples: 2k1*l + k2*l bytes La eficiencia de memoria depende de la relación l/p

– Si l/p es grande: las palabras comparten muchos prefijos.– Si l/p es pequeña: hay pocos prefijos compartidos y se gasta mucha

memoria. En la práctica, mejora l/p > 6

Conclusiones La estructura es adecuada en aplicaciones donde aparezcan

muchos prefijos comunes. El tiempo de ejecución sólo depende (casi) de la longitud de las

palabras, ¡independientemente de cuántas hayan!


34

TAD Árbol

Algunas de las operaciones usuales:– crearÁrbol(árbol T)– árbolVacío(árbol T)– vaciarÁrbol(árbol T)– verÁrbol(árbol T)– insertar(nodo n, nodo padre, árbol T)– borrar(nodo n, árbol T)– borrarSubÁrbol(nodo padre, árbol T)– númeroNodos(árbol T)– profundidad(árbol T)– grado(árbol T)

35

Representando árboles genéricos

No existe una representación única. La representación escogidaviene condicionada fuertemente por el contexto de aplicación y latopología del árbol (grado del árbol, número de nodos, el recorridosobre el árbol, etc.):

– Árboles n-arios Representación directa (no demasiado viable, compleja de manejar) Listas ordenadas de hijos Punteros al padre Hijo más a la izquierda-Hermano de la derecha

– Árboles binarios Hijo izquierdo e hijo derecho para cada nodo: memoria dinámica o sobre

vectores. …

36


Representación directa: cada nodo es una estructuraque entre sus campos tendrá una lista ordenada depunteros a los nodos hijos y si se requiere un punteroal nodo padre.

– ¡¡ Resulta tediosa de manejar !!

ÁrbolInformación estructura,

lista de punteros a hijos,puntero al padre

37


typedef struct // tipo base del árbol{

tipo1 campo1;…; tipoN campoN;struct nodo *padre;lista *hijos;

} nodo;// LISTA NODOS HIJOS typedef struct // tipo base lista{

nodo * hijo;struct nodo_lista *sig;

}nodo_lista; typedef struct{

nodo_lista *inicio;} lista;

// LISTA NODOS HIJOStypedef struct // tipo base lista{

nodo_arbol * hijo;struct nodo_lista *sig;

}nodo_lista; typedef struct{

nodo_lista *inicio;} lista;typedef struct // tipo base del árbol{

tipo1 campo1;…; tipoN campoN;struct nodo_arbol *padre;lista *hijos;

} nodo_arbol;

Opción 1 Opción 2

38


Ambas propuestas anteriores incurren en una paradoja…

– El código de la opción 1 es paradójico porque no se puededeclarar una variable de un tipo de dato –en este caso, el tipolista- cuando aún no ha sido definido.

– El código de la opción 2 es paradójico justamente por lamisma razón que en el caso 1, pero esta vez debido a ladeclaración nodo_arbol *hijo.

El problema viene inducido por culpa de la necesidadde un campo sig en los nodos de una la lista.

– Cuestión: ¿Cómo se podría solucionar?

39


typedef struct // tipo base del árbol{

tipo1 campo1; … tipoN campoN;struct nodo *padre;struct nodo ** hijos;

}nodo ;typedef struct{nodo *raíz;

} arbol;

¡¡ Podemos simular una lista mediante un vector dinámico !!

De esta manera ya no tenemos el problema del puntero sig de una lista sobre memoria dinámica.

hijos será un vector de punteros a nodos del árbol.

void main() {nodo n; // un nodo del árbol con 10 hijosn->hijos=(nodo **) malloc(10*sizeof(nodo *));

}

Podríamos necesitar invocar a la función realloc().

40


Al representar árboles genéricos, por razones demanejabilidad, se suelen hacer ciertas asunciones.Algunas muy comunes son:

1. Fijar un número máximo de hijos por nodo.

2. Fijar un número máximo de nodos en el árbol:

– Se utilizan estrategias de implementación sobre memoria estática

– Aparece el concepto índice del nodo, que es la posición que ocupa un nodo del árbol en el vector.

41


Fijar un número máximo de hijos por nodo:

typedef struct // tipo nodo del árbol{

tipo1 campo1;…tipoN campoN;struct nodo *padre;struct nodo *hijos[n];


} arbol;

typedef struct // tipo nodo del árbol{

tipo1 campo1;…tipoN campoN;struct nodo *padre;struct nodo * hijo1,…,* hijoN;


} arbol;

Opción 1 Opción 2

42


Fijar un número máximo de nodos en el árbol (I).

0

21

3 4

5 76

(índice del nodo)

0

1

2

3

4

5

6

7

21

5 6 7

43

Lista ordenada de nodos hijos. Cada elemento de la lista es el índice de una componente del vector.

En cada componente del vector se almacenaría el contenido del nodo del árbol correspondiente.

43


¡¡ La anterior representación permite visualizar todos los nodos del árbol de una manera directa !!

Simplemente recorriendo las componentes de un vector.

¡¡ En este caso en concreto, un nodo no posee puntero al padre. Aunque se podría modificar la estructura para

guardar esta información !!

¡¡ Nótese que al utilizar memoria estática necesitamos emplear alguna técnica para controlar los “huecos” libres

en el vector !!

44


Ejercicio: Deseamos guardar la edad de los diferentesempleados de una pyme, así como la “posición” del empleadodentro de la jerarquía de la empresa. Se supone que una pyme nopuede tener más de 100 empleados. La jerarquía de la empresaen cuestión, viene representada por el árbol de la figura adjunta.

2

4

5 76

1

3

8

0

109

(jefe)

(subordinado)

45


Escriba la secuencia de instrucciones en C para definir unaestructura de datos que permita modelar el concepto deestructura jerárquica de una PYME cualquiera. Se requiere que apartir de cada trabajador, tener acceso directo a su jefe y a sussubordinados inmediatos.

Sabiendo que para la jerarquía de la ilustración se cumple que: lapersona con índice 0 posee 60 años, las personas ubicadas en elnivel 1 tienen 50 años, las del nivel 2 tienen 40 años a excepciónde las personas ubicadas en el nodo hoja de este nivel queposeen 35 años. Las personas del tercer nivel tienen 30 años ylas personas ubicadas en los nodos hojas restantes 25 años.Escriba la secuencia apropiada de instrucciones en C para crearesta jerarquía.

46


Cuestión: ¿Existe alguna relación entre restringir elnúmero máximo de nodos en el árbol y restringir elnúmero máximo de nodos por niveles?

– Si un árbol va a poseer un máximo de n nodos en total,podemos asegurar que el número de nodos por nivel no va aexceder de n-1. Con lo cual, podríamos utilizar larepresentación de árboles con un número prefijado de hijospor nodo, para representar árboles con un número total denodos prefijado. Aunque, obviamente, estaríamosdesperdiciando una gran cantidad de memoria.

47


Fijar un número máximo de nodos en el árbol (II): punteros al padre

A

CB

D E

F HG

0 1 2 3 4 5 6 7A,0

B,0

C,0

D,1

E,1

F,4

G,4

H,4

A

CB

D E

F HG

Se asume que la componente T[i].indice=i es la raíz del árbol.

T=

árbol T

48


¿ Existe alguna forma de representar árboles de cualquier grado sin asumir

ninguna restricción sobre el número de nodos por hijo o el número de nodos

totales?

49


Utilizando árboles “binarios” * (hijo izquierdo - hermano derecho):

– Aunque resulte paradójico, un árbol n-ario puede serrepresentado mediante un árbol binario.

– Estrategia: cada nodo tendrá dos punteros a nodo (o tres si sedecide mantener un puntero al padre). Uno para referenciar asu hijo situado más a la izquierda, y otro para referenciar a suhermano de la derecha.

– Se puede implementar tanto sobre memoria dinámica comomemoria estática.

* No confundir con elTAD Árbol Binario

50

Representando árboles genéricos: hijo izquierdo - hermano derecho

Especificación informal del TAD Árbol

TAD Árbol[T] es crea, vacio, raiz, padre, hijoIzquierdo, hermanoDerecho, info, insertaHijo, insertaHermano, suprimeHijo, suprimeHermano, modifica, nodoNulo.

Descripción:– Los Árbol[T] son árboles n-arios donde cada nodo contiene un dato

del tipo T. Las posiciones de los nodos en el árbol son del tipo Nodo. Los árboles son modificables: las operaciones insertaHijo e insertaHermano, suprimeHijo y suprimeHermano, modifica añaden, eliminan y modifican respectivamente elementos de un árbol.

51


Operaciones:crea(sal A: Arbol)

Calcula: Devuelve un árbol vacío A.vacio(ent A:Arbol; sal booleano)

Calcula: Devuelve cierto si A es el árbol vacío, y falso en caso contrario.raiz(ent A:Arbol; sal Nodo)

Calcula: Devuelve el nodo raíz en el árbol A. Si el árbol A está vacío, devuelve nulo.

padre(ent A:Arbol; P:Nodo; sal Nodo)Requiere: El árbol A es no vacío y P no es nodo nulo.Calcula: Devuelve el nodo padre del nodo P en el árbol A. Si P es la raíz devuelve nulo.

52


hijoIzquierdo(ent A:Arbol; P:Nodo; sal Nodo)Requiere: El árbol A es no vacío y P no es nodo nulo.Calcula: Devuelve el nodo hijo más a la izqda. del nodo P en el árbol A. Si el nodo P no tiene hijos, devuelve nulo.

hermanoDerecho(ent A:Arbol; P: Nodo; sal Nodo)Requiere: El árbol A es no vacío. P no es nodo nulo.Calcula: Devuelve el nodo hermano derecho del nodo P en el árbol A. Si el nodo P no tiene hermano derecho, devuelve nulo.

info(ent A:Arbol; P: Nodo; sal elem: T)Requiere: El árbol A es no vacío. P no es nodo nulo.Calcula: Devuelve en elem el contenido del nodo P en el árbol A.

53


insertaHijo(ent A:Arbol; P: Nodo; elem:T)Requiere: Si el árbol A es no vacío, entonces P no es nodo nulo.Modifica: A.Calcula: Añade un nodo, con contenido elem, como hijo más a la izquierda del nodo P en el árbol A. Si el árbol A es vacío, entonces añade un nodo con contenido elem como raíz del árbol A.

insertaHermano(ent A:Arbol; P: Nodo; elem: T)Requiere: El árbol A es no vacío. P no es nodo nulo. P no es la raiz. Modifica: A.Calcula: Añade un nodo, con contenido elem, como hermano derecho del nodo P en el árbol A.

nodoNulo(ent P: Nodo; sal booleano)Calcula: Devuelve cierto si P es nulo, y falso en caso contrario.

54


suprimeHijo(ent A:Arbol; P: Nodo)Requiere: El árbol A es no vacío. El nodo P no es nulo.Modifica: A.Calcula: Suprime el hijo más a la izquierda del nodo P en el árbol A y todos sus descendientes.

suprimeHermano(ent A:Arbol; P: Nodo)Requiere: El árbol A es no vacío. El nodo P no es nulo.Modifica: A.Calcula: Suprime el hermano derecho del nodo P en el árbol A y todos sus descendientes.

modifica(ent A:Arbol; P: Nodo; Elem: T)Requiere: El árbol A es no vacío. El nodo P no es nodo nulo.Modifica: A.Calcula: Modifica el contenido del nodo P en el árbol A, cambiándolo por el nuevo contenido elem.

55


A

CB

D E

F HG

A

CB

D E

F HG

raíz

Memoria dinámica

typedef struct{tipo1 elem1; … tipoN elemN;struct nodo * hijo_izq, * herm_der;

} nodo;

56

Representando árboles genéricos:hijo izquierdo - hermano derecho

A

CB

D E

F HG

raíz

Memoria dinámica(incluyendo puntero al padre)

typedef struct{tipo1 elem1; … tipoN elemN;struct nodo * hijo_izq, * herm_der, * padre;

} nodo;

VER arbol.c

57

Representando árboles genéricos:hijo izquierdo - hermano derecho

A

CB

D E

F HG

hijo_izq elem herm_der

0 4 B 3

1 0 A -1

2 6 E -1

3 -1 C -1

4 -1 D 2

5 -1 G 7

6 -1 F 5

7 -1 H -1

Memoria estática

Raíz

¡¡ Evidentemente, el número de nodos del árbol queda fijado al número de componentes del vector !!

58


Sobre la representación usando memoria estática …– Cuestión: ¿Cómo identificamos un nodo hoja?

Por definición, un nodo hoja es aquel que no tiene hijos, y por lo tanto, es condición necesária y suficiente que el valor del campo hijo_izq sea –1 *.

– Cuestión: ¿Cómo identificamos el nodo raíz? Resulta imposible porque la representación no informa en

absoluto de los nodos ascendientes de un nodo dado, por lo tanto necesitamos una variable auxiliar que indique qué componente del vector se corresponde con el nodo raíz del árbol.

* Como la especificacióndice que devuelve nulo, laimplementación conmemoria estática y Nodo de tipo enteropuede tomar comovalor nulo = -1. En Cse debería definir una cte: #define NULO = -1

Mirar en arbol.c la Implementación con memoria dinámica, para ver cómo está definido el tipo nodo.

59


Sobre la representación usando memoria estática …– Ejercicio: Dado un nodo cualquiera, ¿Cómo podemos

averiguar la posición en el vector del nodo padre? Sugerencia: a excepción del nodo raíz, todos los los nodos

restantes poseen un nodo padre. Implementa una solución algorítmica en pseudo-código.

– Ejercicio: Implementa en C la estructura de datos para representar un árbol cualquiera. Supóngase que elem es de un tipo ya predefinido.

– Cuestión: ¿Cómo podemos modificar la estructura para que cada nodo guarde la posición de su nodo padre? Añadir una columna más en el vector de la estructura que

almacene la posición del padre de un nodo. El nodo raíz tendrá a-1 esta columna.

60

Recorrido sobre árboles genéricos

Hay varias posibilidades para recorrer los nodos de un árbol genérico:

– Primero en profundidad: Exploramos el árbol hasta llegar a un nodo hoja al mismo tiempo

que nos anotamos por cada nodo, que visitamos hasta llegar aeste nodo hoja, los nodos hijos pendientes por explorar.

3 posibilidades: preorden (nodo actual, subárbol izquierdo, restode subárboles derechos), inorden (subárbol izquierdo, nodoactual, resto de subárboles derechos), postorden (subárbolizquierdo, resto de subárboles derechos, nodo actual).

– Primero en anchura o amplitud: Recorremos el árbol por niveles.

– Estrategias combinadas: Combinan las dos anteriores.

61

Árboles binarios

Árboles binarios– Un árbol binario es un árbol con raíz en el que cada nodo

tiene como máximo dos hijos.– Árbol de grado 2. A cada uno de los subárboles se les llama

subárbol izquierdo y subárbol derecho.– Un árbol binario completo es un árbol en el que cada nodo

tiene cero o dos hijos.– Un árbol binario perfecto es un árbol binario completo en el

que todas las hojas tienen la misma profundidad (distancia desde la raíz, también llamada altura).

62

Árboles binarios

Árboles binarios– Cada nodo puede tener hasta dos ramas.– Se admite el concepto de árbol binario vacío: cuando el número de

nodos es cero– Definición: conjunto finito de nodos que; o bien está vacío o consiste

en una raíz y dos árboles binarios disjuntos llamados subárbol izquierdo y subárbol derecho (diferencia de árboles genéricos).

K

63


Especificación informal del TAD Árbol Binario

TAD ÁrbolBinario[T] es crea, vacio, raiz, padre, hijoIzquierdo, hijoDerecho, info, insertaIzqdo, insertaDerecho, suprimeIzqdo, suprimeDerecho, modifica, nodoNulo.

Descripción:– Los ÁrbolBinario[T] son árboles binarios donde cada nodo contiene

un dato del tipo T. Los nodos en el árbol son del tipo Nodo. Los árboles son modificables: las operaciones insertaIzqdo e insertaDerecho, suprimeIzqdo y suprimeDerecho, modifica añaden, eliminan y modifican respectivamente elementos de un árbol.

64


Operaciones:crea(sal A: ArbolBinario)

Calcula: Devuelve un árbol vacío A.vacio(ent A:ArbolBinario; sal booleano)

Calcula: Devuelve cierto si A es el árbol vacío, y falso en caso contrario.raiz(ent A:ArbolBinario; sal Nodo)

Calcula: Devuelve el nodo raíz en el árbol A. Si el árbol A está vacío, devuelve nulo.

padre(ent A:ArbolBinario; P:Nodo; sal Nodo)Requiere: El árbol A es no vacío y P no es nodo nulo.Calcula: Devuelve el nodo padre del nodo P en el árbol A. Si P es la raíz devuelve nulo.

65


hijoIzquierdo(ent A:ArbolBinario; P:Nodo; sal Nodo)Requiere: El árbol A es no vacío y P no es nodo nulo.Calcula: Devuelve el nodo hijo izquierdo del nodo P en el árbol A. Si el nodo P no tiene hijo izquierdo, devuelve nulo.

hijoDerecho(ent A:ArbolBinario; P:Nodo; sal Nodo)Requiere: El árbol A es no vacío. P no es nodo nulo.Calcula: Devuelve el nodo hijo derecho del nodo P en el árbol A. Si el nodo P no tiene hijo derecho, devuelve nulo.

info(ent A:ArbolBinario; P:Nodo; sal elem: T)Requiere: El árbol A es no vacío. P no es nodo nulo.Calcula: Devuelve en elem el contenido del nodo P en el árbol A.

66


insertaIzqdo(ent A:ArbolBinario; P:Nodo; elem:T)Requiere: Si el árbol A es no vacío, entonces el nodo P es no nulo y el nodo hijo izquierdo de P es nuloModifica: A.Calcula: Añade un nodo, con contenido elem, como hijo izquierdo del nodo P en el árbol A. Si el árbol A es vacío, entonces añade un nodo con contenido elem como raíz del árbol A.

insertaDerecho(ent A:ArbolBinario; P:Nodo; elem: T)Requiere: El árbol A es no vacío. El nodo P es no nulo. El nodo hijo derecho de P es nulo. Modifica: A.Calcula: Añade un nodo, con contenido elem, como hijo derecho del nodo P en el árbol A.

nodoNulo(ent P:Nodo; sal booleano)Calcula: Devuelve cierto si P es nulo, y falso en caso contrario.

67


suprimeIzqdo(ent A:ArbolBinario; P:Nodo)Requiere: El árbol A es no vacío. El nodo P no es nulo.Modifica: A.Calcula: Suprime el hijo izquierdo del nodo P en el árbol A y todos sus descendientes.

suprimeDerecho(ent A:ArbolBinario; P:Nodo)Requiere: El árbol A es no vacío. El nodo P no es nulo.Modifica: A.Calcula: Suprime el hijo derecho del nodo P en el árbol A y todos sus descendientes.

modifica(ent A:ArbolBinario; P:Nodo; Elem: T)Requiere: El árbol A es no vacío. El nodo P no es nodo nulo.Modifica: A.Calcula: Modifica el contenido del nodo P en el árbol A, cambiándolo por el nuevo contenido elem.

68

Recorrido sobre árboles binarios

Ejercicio: desarrollar en pseudo-código un método para explorar en profundidad un árbol binario.

69

Recorrido sobre árboles binarios

Ejemplo: código para explorar el árbol en inorden.

funcion inorden(nodo) inicio

si(existe(nodo)) inicio

inorden(hijoIzqdo(nodo)); visitar(nodo); inorden(hijoDerecho(nodo));

fin; fin;

void inorden(Arbol *A, nodo *p) { if (p != NULL) {

inorden(A, hijoIzqdo(A, p)); tratar(A, p); inorden(A, hijoDerecho(A, p)); }

}

VER arbolbinario.c

Documents

273690 Tema 05 Arboles Parte I