Nodos

Arturo Díaz Pérez

Análisis y Complejidad de Algoritmos

Arboles Binarios
Arturo Díaz Pérez ¬ ® ¯ ° Arboles Definiciones Recorridos Arboles Binarios Profundidad y Número de Nodos

Análisis y Diseño de Algoritmos

Arboles-1

Arbol
F Un árbol es una colección de elementos, llamados nodos, uno de los cuales se distingue con el nombre de raíz, los cuales mantienen una relación(parentezco) que define una estructura jerárquica entre ellos. F De manera formal, un árbol se puede definir en forma recursiva mediante las reglas siguientes:
ß El conjunto vacío de nodos es un árbol, llamado nulo o vacío. ß Un nodo es un árbol, el cual es, asimismo, la raíz del árbol. ß Si n, es un nodo y T1, T2, . . . , Tk son árboles con raíces n1, n2, . . . , nk, respectivamente, se puede construir unnuevo á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 como los hijos del nodo n.
Análisis y Diseño de Algoritmos Arboles-2

Análisis y Complejidad de Algoritmos

1

Arturo Díaz Pérez

Ejemplo
ß Si n, es un nodo y T1, T2, . . . , Tk son árboles con raíces n1,n2, . . . , nk, respectivamente, se puede construir 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 como los hijos del nodo n.
n

n1

n

2

nk

T1
Análisis y Diseño de Algoritmos

T2

Tk
Arboles-3

Algunas Definiciones
F Un camino de unnodo n1 a un nodo nk es una secuencia de nodos n1, n2, ... , nk de tal manera que ni es padre de ni+1 para i = 1, 2, . . . , k-1. F La longitud de un camino es uno menos que el número de nodos en el camino.
ß Existe un camino de longitud 0 de un nodo a sí mismo.

F Si existe un 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. F Unancestro o descendiente de un nodo diferente de sí mismo se dice que es un ancestro o descendiente propio, respectivamente.
Análisis y Diseño de Algoritmos Arboles-4

Análisis y Complejidad de Algoritmos

2

Arturo Díaz Pérez

Algunas Definiciones
F En un árbol la raíz es el único nodo que no tiene ancestros propios. F Un nodo sin descendientes propios se conoce como una hoja. F Un subárbolde un árbol es un nodo junto con todos sus descendientes. F El peso de un nodo en un árbol es la longitud del camino más largo del nodo a una hoja. F El peso de un árbol es el peso de la raíz. F La profundidad de un nodo es la longitud del camino único de la raíz al nodo. F La profundidad de un árbol es la profundidad de la hoja más profunda. Arboles-5 Análisis y Diseño de Algoritmos

RecorridosF Al visitar los nodos de un árbol existen algunas maneras útiles en las que se pueden ordenar sistemáticamente los nodos de un árbol. F Los ordenamientos más importantes son llamados: preorden, post-orden y en-orden y se definen recursivamente como sigue:
ß Si un árbol T es nulo, entonces, la lista vacía es el listado preorden, post-orden y en-orden del árbol T. ß Si T consiste de un sólo nodon, entonces, n es el listado preorden, post-orden y en-orden del árbol T.
Análisis y Diseño de Algoritmos Arboles-6

Análisis y Complejidad de Algoritmos

3

Arturo Díaz Pérez

Recorridos
n

T1

T2

Tk

F Si T es un árbol con raíz n y subárboles T1, T2, . . . , Tk, entonces,
ß El listado pre-orden de los nodos de T es la raíz n, seguida por los nodos de T1 en pre-orden, despuéslos nodos de T2 en preorden, y así, hasta los nodos de Tk en pre-orden. ß El listado post-orden de los nodos de T es los nodos de T1 en postorden, seguidos de los nodos de T2 en post-orden, y así hasta los nodos de Tk en post-orden, todos ellos seguidos de n. ß El listado en-orden de los nodos de T es los nodos de T1 en-orden, seguidos por n, seguidos por los nodos de T2, . . . , Tk, cada grupo...