arboles
TRANSCRIPT
ING. EN SISTEMAS COMPUTACIONALES
III Semestre
Tema V. Árboles
Institu
to d
e E
stu
dio
s S
up
erio
res
del Is
tmo
de T
ehuan
tepec
Docente:
M.I. Blanca Elia Jiménez Guzmán
Los datos presentan frecuentemente
relaciones de jerarquía entre ellos.
La estructura de datos que refleja
esta relación recibe el nombre de
grafo en árbol o simplemente
árbol.
2M.I. Blanca Elia Jiménez Guzmán
Es una estructura de datos no lineal,
Se usa principalmente para
representar datos con una relación
jerárquica entre sus elementos,
como por ejemplo registros, árboles
genealógicos y tablas de contenidos.
3M.I. Blanca Elia Jiménez Guzmán
Ejemplo de árboles genealógicos:
“Me casé con una viuda que tenía una hija mayor. Mi
padre, quien nos visitaba muy a menudo, se enamoró
de mi hijastra y se casó con ella. En consecuencia, mi
padre se convirtió en mi yerno y mi hijastra pasó a ser
mi madre. Algunos meses después, mi esposa dio a luz
un hijo, quien se convirtió en el cuñado de mi padre
así como en mi tío. La esposa de mi padre, que es mi
hijastra, también tuvo un hijo. Por lo tanto, tuve un
hermano y al mismo tiempo un nieto. Mi esposa es mi
abuela, ya que ella es la madre de mi madre. Por
consiguiente, soy el marido de mi esposa y al mismo
tiempo su medio nieto, en otras palabras, soy mi
propio abuelo.”
Por Niklaus Wirth4M.I. Blanca Elia Jiménez Guzmán
Un árbol binario, puede ser
representado fácilmente en una
computadora.
El árbol binario se define como un
conjunto finito de elementos,
llamados nodos, los cuales se pueden
subdividir en 0, 1 o 2 nodos más
llamados subárboles.
5M.I. Blanca Elia Jiménez Guzmán
6M.I. Blanca Elia Jiménez Guzmán
H Y
D Q
C G O W
A P
R E N
M NIVEL 0
NIVEL 1
NIVEL 2
NIVEL 3
Frecuentemente se usa una terminología de
relaciones familiares para describir las
relaciones entre los nodos de un árbol. En
particular, suponga que D, es un nodo de M,
con un sucesor izquierdo C y un sucesor
derecho G. Entonces D se llama padre de C
y G. Análogamente, C se llama hijo
izquierdo de D y G es el hijo derecho de D.
Se dice que C y G son hermanos. Cada nodo
de un árbol binario excepto la raíz, tiene
un único padre, llamado predecesor.
7M.I. Blanca Elia Jiménez Guzmán
También se usa terminología de grafos y
de horticultura para un árbol binario.
La línea dibujada entre un nodo padre y
un sucesor, se llama arista y una
secuencia de aristas consecutivas se llama
camino.
Un nodo terminal se llama hoja y un
camino que termina en una hoja se llama
rama.
8M.I. Blanca Elia Jiménez Guzmán
Cada nodo de un árbol binario, tiene
asignado un número de nivel, aquellos
nodos con el mismo número de nivel se
dice que pertenecen a la misma
generación.
La profundidad (o altura) de un árbol, es
el número máximo de nodos de una rama,
equivale a 1 más que el mayor número de
nivel del árbol.
9M.I. Blanca Elia Jiménez Guzmán
10M.I. Blanca Elia Jiménez Guzmán
Recorrido
Preorden Inorden Postorden
11M.I. Blanca Elia Jiménez Guzmán
Procesa la raíz
Recorrer subárbol izquierdo en preorden
Recorrer subárbol derecho en preorden
Preorden
12M.I. Blanca Elia Jiménez Guzmán
Recorrer subárbol izquierdo en inorden
Procesa la raíz
Recorrer subárbol derecho en inorden
Inorden
13M.I. Blanca Elia Jiménez Guzmán
Recorrer subárbol izquierdo en postorden
Recorrer subárbol derecho en postorden
Procesa la raíz
Postorden
M.I. Blanca Elia Jiménez Guzmán 14
E-mail: [email protected]
“La mente es como un paracaídas, nosirve de nada si no se abre”.
Anónimo