Clase 9 EDD

Diseño de Estructuras de Datos
Analista Programador Computacional

Profesor: Paula Castro
5 Octubre 2015

ARBOLES

Definición
Los árboles son una de las estructuras de datos no lineales más utilizada.
Sirve para representar estructuras de información jerárquicas y direcciones o
etiquetas de una manera organizada.
Dentro de la ciencia de la computación, los árboles tienen muchas
aplicaciones,como, por ejemplo:
o organizar tablas de símbolos en compiladores
o representar tablas de decisión
o asignar bloques de memoria de tamaño variable
o ordenar
o buscar
o solucionar juegos
o probar teoremas
Los árboles permiten representar situaciones de la vida diaria como son:
o organización de una empresa
o árbol genealógico de una persona
o organización de torneos deportivos

Representación
Unárbol puede representarse gráficamente de muchas formas. Algunas de
ellas son por medio de:

Representación
La forma más común de representar a los árboles es por medio de un grafo
con la raíz hacia arriba:

Consideraciones

• Cada vértice o nodo del árbol puede tener un nombre y puede tener una
información asociada; un arco es una conexión entre dos vértices.
• Un camino en un árbol es una lista devértices diferentes en los que
vértices sucesivos están conectados por arcos en el árbol. Una
propiedad que define a los árboles es que existe exactamente un camino
entre la raíz y cada uno de los otros nodos en el árbol.
• La longitud de un camino es el número de nodos del camino menos uno.
Por tanto, hay un camino de longitud cero de cualquier nodo a si mismo.

Consideraciones
• Se dice que unnodo Y está abajo de un nodo X, si X está en el camino de
Y a la raíz.
• Además, cada nodo, excepto la raíz, tiene exactamente un nodo arriba de
él, que es llamado su padre; los nodos que están exactamente abajo de él
son llamados sus hijos.
• El número de hijos que cuelgan de un nodo es llamado el grado del nodo.
El grado de un árbol es el grado máximo de los nodos del árbol. Un nodo
de gradocero es llamado hoja, es decir, no tiene hijos

Ejemplo

• El camino del nodo A al nodo P es (A, B, D, J, P), cuya longitud de camino
es 4.
• El nodo E es el padre de K y L.
• Los hijos de G son M, N y O.
• Los nodos de grado 0 son: I, P, K, L, F, M, N, O, y H es decir son las hojas
del árbol.
• El único nodo de grado 1 es J.
• Los nodos de grado 2 son A, B, D y E.
• Los nodos de grado 3 son C yG.
• No existen nodos de mayor grado, por tanto, el grado del árbol es 3.

Los nodos de un árbol pueden dividirse en niveles; el nivel de un nodo es el
número de nodos en el camino de él a la raíz. La altura de un árbol es el
nivel máximo de todos los nodos en el árbol, es decir, la distancia máxima de
la raíz a cualquier nodo.
Por ejemplo:

De lo anterior, se ve que el árbol es de altura 4.
Enmuchas ocasiones los árboles se estudian por su grado. En este caso,
estudiaremos los árboles de grado 2, es decir, los árboles binarios.
Nota: Altura, Profundidad son sinónimos de niveles.

Árbol Binario
Los árboles binarios son el caso particular más simple. Son usados para
representar ciertos tipos de expresiones algebraicas, algoritmos, búsquedas
y ordenamientos. Para definirlos formalmente,podríamos decir que un
conjunto T de elementos (nodos) es un árbol binario si:
1. T es vacío, o
2. T está particionado en 3 conjuntos disjuntos
a) un solo elemento R, llamado la raíz
b) 2 conjuntos que son árboles binarios, llamados los subárboles
izquierdo y
derecho de R
De esta forma, T es un árbol binario si:
1. T no tiene nodos, o
2. T es de la forma:

Recorrido de árboles binarios
Para recorrerun árbol, existen varias formas de lograrlo, las 3 más comunes son
preorden, in-orden y post-orden.
Para recorrer un árbol binario no vacío T en pre-orden o previo:
1. visitar la raíz
2. recorrer recursivamente el subárbol izquierdo
3. recorrer recursivamente el subárbol derecho
Para recorrer un árbol binario no vacío T en in-orden o simétrico:
1. recorrer recursivamente el subárbol izquierdo...