Estructura
CURSO: D-309 ”21”
MATERIA: ESTRUCUTURA DE DATOS
DEBER
1.-DEFINICION DE ARBOLES (TDA)
Un árbol es una colección de elementos, llamados nodos, de los cuales sedistingue con el nombre de raíz.
Los nodos mantienen entre ellos una relación que define una estructura jerárquica (de “paternidad”) entre ellos.
Recursivamente: un árbol puede verse como unaestructura formada por la raíz de dicho árbol y una lista de árboles (los hijos).
Este nodo raíz es el padre de las raíces de los árboles que componen la lista, a partir del cual, se establece la relación depaternidad entre ellos.
El conjunto vacío de nodos es un árbol, llamado nulo o vacío.
Si n es un nodo y A1, A2 , . . . , Ak son árboles con raíces n1 ,n2 , . . . , nk , respectivamente, se puedeconstruir un nuevo árbol haciendo n el padre de los nodos n1 , n2 , . . . , nk .
En este árbol n es la raíz y T1, T2,. . ., Tk son los subárboles de la raíz. Los nodos n1, n2,. . ., nk se conocen comolos hijos del nodo n.
2.- QUE SON LOS RECORRIDOS DE ARBOLES
Al recorrer los nodos de un árbol se consideran ciertas formas útiles para ordenar sistemáticamente los nodos de un árbol.
Los modosde realizar los recorridos en profundidad más importantes son llamados: pre-orden, post-orden y en-orden y se definen recursivamente como sigue:
El recorrido pre-orden de los nodos de A es la raíz n,seguida por los nodos de A1 en pre-orden, después los nodos de A2 en pre-orden, y así, hasta los nodos de Ak en pre-orden.
El recorrido post-orden de los nodos de A son los nodos de A1 en post-orden,seguidos de los nodos de A2 en post-orden, y así hasta los nodos de Ak en post-orden, todos ellos seguidos de n.
El recorrido en-orden de los nodos de A son los nodos de A1 en-orden, seguidos por n,seguidos por los nodos de A2,. . ., Ak, cada grupo de nodos en-orden.
A estos recorridos se les agrega el recorrido ‘en amplitud’ que corresponde a un recorrido ‘por niveles ‘del árbol.
3.-...
Regístrate para leer el documento completo.