Download Algoritmos y estructura de datos en I.O.

Algoritmos y estructura
de datos en I.O.
Arboles Generales
INTRODUCCIÓN
• Hasta ahora las estructuras de datos que hemos estudiado eran de tipo lineal,
o sea, existía una relación de anterior y siguiente entre los elementos que la
componían(cada elemento tendrá uno anterior y otro posterior , salvo los
casos de primero y último).Pues bien, aquí se va a estudiar una estructuración
de los datos más compleja: los árboles.
Para tratar esta estructura cambiaremos la notación:
Las listas tienen posiciones. Los árboles tienen nodos.
Las listas tienen un elemento en cada posición. Los árboles tienen una etiqueta en cada nodo (algunos
autores distinguen entre árboles con y sin etiquetas.
Un árbol sin etiquetas tiene sentido aunque en la inmensa mayoría de los problemas necesitaremos
etiquetar los nodos.
Es por ello por lo que a partir de ahora sólo haremos referencia a árboles etiquetados).
Implementación física.
Consideremos el ejemplo de la siguiente figura.
Podemos observar que cada uno de los identificadores representa un nodo y la relación padrehijo se señala con una línea. Los árboles normalmente se presentan en forma descendente y se
interpretan de la siguiente forma:
•
•
•
•
•
E es la raíz del árbol.
S1,S2,S3 son los hijos de E.
S1,D1 componen un subárbol de la raíz.
D1,T1,T2,T3,D3,S3 son las hojas del árbol.
etc...
RECORRIDOS DE UN ÁRBOL
• Listado preorden.
A=Ar=rAvAs=rvAuAwAs= rvuAwAs=rvuwAxAyAzAs=
rvuwxAyAzAs=rvuwxyAzAs=rvuwxyzAs =rvuwxyzsApAq=rvuwxyzspAq=rvuwxyzspq.
• Listado postorden.
A=Ar=AvAsr=AuAwvAsr= uAwvAsr=uAxAyAzwvAsr=
uxAyAzwvAsr=uxyAzwvAsr=uxyzwvAsr= uxyzwvApAqsr=uxyzwvpAqsr=uxyzwvpqsr.
• Listado inorden.
A=Ar=AvrAs=AuvAwrAs= uvAwrAs=uvAxwAyAzrAs=uvxw
AyAzrAs=uvxwyAzrAs=uvxwyzrAs= uvxwyzrApsAq=uvxwyzrpsAq=uvxwyzrpsq.
Los resultados de los listados de pre-orden,
post-orden e in-orden son los siguientes:
• Finalmente es interesante conocer que un árbol no puede, en general,
recuperarse con uno solo de sus recorridos. Por ejemplo: Dada la lista en
inorden:vwyxzrtupsq,los árboles de la figura 4 tienen ese mismo recorrido en
inorden.
UNA IMPLEMENTACIÓN MATRICIAL
• Sea A un árbol en el cual los nodos se etiquetan 0,1,2,...,n-1,es decir, cada nodo contiene un
campo de información que contendrá estos valores. La representación más simple de A que
soporta la operación PADRE es una matriz lineal P en la cual el valor de P[i] es un valor o un
cursor al padre del nodo i. La raíz de A puede distinguirse dándole un valor nulo o un valor a él
mismo como padre. Por ejemplo, podemos usar un esquema de cursores donde P[i]=j si el
nodo j es el padre del nodo i, y P[i]=-1 (suponemos que NODO_NULO=-1) si el nodo i es la
raíz. La definición del tipo sería:
•
•
•
•
#define MAXNODOS 100
/*Por ejemplo*/
#define NODO_NULO -1
typedef int nodo;
typedef int *ARBOL;
/*Indica una casilla de la matriz*/
IMPLEMENTACIÓN DE ÁRBOLES
POR LISTAS DE HIJOS
• Una forma útil e importante de representar árboles es formar para cada nodo
una lista de sus hijos. Las listas pueden representarse por cualquier método,
pero como el número de hijos que cada nodo puede tener puede ser variable,
las representaciones por listas enlazadas son las más apropiadas. La figura 8
sugiere como puede representarse el árbol del ejemplo de la figura 7: