Tda pila

Algoritmos y Programación II - 7504 Arboles:

Curso 2006

Un árbol es una colección de elementos, llamados nodos, uno de los cuales se distingue 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 una estructura 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 de paternidad entre ellos. El conjunto vacío de nodos es un árbol, llamado nulo o vacío. Si n es un nodo y A 1 , A 2 , . . . , A k son árboles con raíces n 1 ,n 2 , . . . , n k , respectivamente, se puede construir un nuevo árbol haciendo n el padre de los nodosn 1 , n 2 , . . . , n k . En este árbol n es la raíz y T 1 , T 2 , . . . , T k son los subárboles de la raíz. Los nodos n 1 , n 2 , . . . , n k se conocen como los hijos del nodo n. Definiciones: camino de un nodo n a un nodo m: es una secuencia de nodos n 1 , n 2 , ... , m de tal manera que n i es padre de n i+1 para i = 1, 2, . . . , k-1. longitud de un camino: es el número de nodos en el caminomenos uno. El camino de un nodo a si mismo mide 0. Si existe camino de un nodo a a un nodo b, entonces se dice que a es un ancestro de b y que b es un descendiente de a. Un ancestro o descendiente de un nodo diferente de sí mismo se dice que es un ancestro o descendiente propio, respectivamente.En un árbol la raíz es el único nodo que no tiene ancestros propios. hoja: nodo sin descendientespropios. subárbol de un árbol: es un nododel árbol junto con todos sus descendientes. profundidad de un nodo: longitud del camino único de la raíz al nodo. profundidad de un árbol: profundidad de la hoja más profunda. grado de un nodo (Grado de salida de un nodo): número de hijos que tiene. El grado de un nodo hoja es cero. altura de un nodo en un árbol: la longitud del mayor de los caminos del nodo acada hoja. La altura de un árbol es la altura de la raíz. profundidad de un nodo: longitud del único camino de la raíz a ese nodo. niveles de un árbol: dado un árbol de altura h se definen los niveles 0...h de modo que el nivel i está compuesto por todos los nodos de profundidad i. orden de los nodos: los hijos de un nodo usualmente están ordenados de izquierda a derecha. Si se desea ignorar elorden de los dos hijos, se habla de un árbol no-ordenado.

1

Algoritmos y Programación II - 7504

Curso 2006

Al recorrer los nodos de un árbol se consideran ciertas formas útiles para ordenar sistemáticamente los nodos de un árbol. Los modos de realizar los recorridos en profundidad más importantes son llamados: pre-orden, post-orden y en-orden y se definen recursivamente como sigue: Elrecorrido preorden de los nodos de A es la raíz n, seguida por los nodos de A 1 en pre-orden, después los nodos de A 2 en pre-orden, y así, hasta los nodos de A k en pre-orden. El recorrido postorden de los nodos de A es los nodos de A 1 en post-orden, seguidos de los nodos de A 2 en post-orden, y así hasta los nodos de A k en post-orden, todos ellos seguidos de n. El recorrido inorden de los nodosde A es los nodos de A 1 en-orden, seguidos por n, seguidos por los nodos de A 2 , . . . , A k , 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. EL TDA ARBOL Usaremos un valor especial ARBOL_VACIO para el caso en que el árbol no contenga nodos, y NODO_NULO para expresar que un nodo no existe.Primitivas del TDA Arbol CREAR_Arbol: crea un árbol. Precondición : no tiene Postcondición.: el árbol vacío. DESTRUIR. libera los recursos que mantienen el árbol . Precondición: el árbol debe haber sido creado PADRE (de un nodo): esta función recibe el valor de un nodo y devuelve el padre del nodo en el árbol. Si el nodo no tiene padre, devuelve NODO_NULO Precondición: el nodo pasado al método no es...