Árboles N-Arios

Árboles N-arios

(Lecciones 15 y 17…)

Conceptos, definiciones y terminología básica
• Árbol:
– Conjunto de elementos de un mismo tipo,
denominados nodos, que pueden representarse en un grafo no orientado, conexo y acíclico, en el que existe un vértice destacado denominado raíz
• Por lo general es una estructura jerárquica…

– Definición recursiva:
• Un árbol n-ario (con n≥1) es unconjunto no vacío de
elementos del mismo tipo tal que: – Existe un elemento destacado llamado raíz del árbol – el resto de los elementos se distribuyen en m subconjuntos
disjuntos (0 ≤m ≤n ), llamados subárboles del árbol original, cada uno de los cuales es a su vez un árbol n-ario

Conceptos, definiciones y terminología básica
• Árbol ordenado:
– Si en el conjunto de subárboles de un árboln-ario se supone definida una relación de orden total, el árbol se denomina ordenado

Árbol ordenado con raíz X y subárboles A1 … Am Leyenda: Nodo Árbol

Árbol 3-ario de números enteros

Conceptos, definiciones y terminología básica
• Bosque:
– Un bosque ordenado de grado n (con n≥1) es una
secuencia A1, …Am, con 0 ≤m ≤n , de árboles n-arios ordenados. • Si m=0, el bosque se llama vacío– Un árbol n-ario se genera a partir de un elemento y un
bosque ordenado de grado n, bastando considerar el elemento como raíz del árbol, y el bosque como subárboles

– Los bosques se generarán como secuencias de árboles, a
partir de un bosque vacío, y una operación de añadir por la derecha un árbol a un bosque

Especificación Algebraica
espec árbolesOrdenados usa booleanos,naturalesparámetro formal género elmto fpf géneros bosque, árbol operaciones [ ]: −> bosque +dch: bosque árbol −> bosque

Generadoras de bosque (cnj. libre)

long: bosque −> nat parcial _[_]: bosque nat −> árbol parcial resto: bosque −> bosque {=el bosque menos el 1er árbol} plantar: elmto bosque −> árbol ….
Generadora de árbol (cnj. libre)

Especificación Algebraica
… raíz: árbol −> elmto bosq: árbol−> bosque parcial subárbol: árbol nat −> árbol numHijos: árbol −> nat hoja?: árbol −> bool altBosque: bosque −> nat altÁrbol: árbol −> nat dominios de definición b:bosque; i:nat; e:elmto; a:árbol b[i] está definido sólo si (1≤i)∧(i≤long(b)) resto(+dch(b,a)) subárbol(plantar(e,b),i) def. sólo si (1≤i)∧(i≤long(b))

…..

Especificación Algebraica
… ecuaciones b:bosque; a:árbol; i:nat; e:elmtolong([ ]) = 0 long(+dch(b,a)) = suc(long(b)) i=suc(long(b)) −> +dch(b,a)[i] = a i≠suc(long(b)) −> +dch(b,a)[i] = b[i] resto(+dch([ ],a)) = [ ] resto(+dch(+dch(b,a1),a2)) = +dch(resto(+dch(b,a1)),a2) …..

Especificación Algebraica
… raíz(plantar(e,b)) = e bosq(plantar(e,b)) = b subárbol(plantar(e,b),i) = b[i] numHijos(plantar(e,b)) = long(b) hoja?(a) = (numHijos(a) = 0) altBosque([ ]) = 0altBosque(+dch(b,a)) = max(altBosque(b),altÁrbol(a)) hoja?(a) −> altÁrbol(a) = 0 not hoja?(a) −> altÁrbol(a) = suc(altBosque(bosq(a))) fespec

Recorridos en árboles n-arios
Un recorrido de un árbol consiste en visitar todos los Raíz 1 elementos del árbol una sola vez. • Recorridos en profundidad: – Recorrido en pre-orden: 2 … An N+1 A1 1. se visita la raíz 2. se recorren en pre-orden todos lossubárboles, deN+1
izquierda a derecha
Raíz

–

1. se recorren en post-orden todos los subárboles, de
izquierda a derecha 2. se visita la raíz

Recorrido en post-orden:

1
A1

N

…

An

•
– –

El recorrido en anchura de un árbol consiste en visitar todos los elementos del árbol una sola vez, de la forma:
primero se visitan los elementos del nivel 0, luego los del nivel 1, y asísucesivamente, En cada nivel, se visitan los elementos de izquierda a derecha

Especificación Algebraica - Recorridos
espec recorridosÁrbolesOrdenados usa árbolesOrdenados,listas {de elementos} operaciones
preBosque, postBosque: bosque lista preorden, postorden: árbol lista
1 2
A1 Raíz

…
N+1

An

N+1

Raíz

ecuaciones b:bosque; a:árbol; e:elemento

1
An

N

A1 …...