Arboles

ÁRBOLES
INSTITUTO TECNOLÓGICO DE VERACRUZ
INGENIERÍA MECATRÓNICA
Programación en Tiempo Real
NON-ACTIVATED VERSION
Unidad II
www.avs4you.com

M.C. Ofelia Gutiérrez Giraldi

Índice...2.1 Definición de un árbol.
2.2 Terminología y caracterización de los árboles.
NON-ACTIVATED VERSION
2.3 Árboles de expansión mínimos.
2.4 Árboles Binarios.
www.avs4you.com
2.5 Recorridos en unárbol
2.6 Árboles de decisión y el tiempo mínimo para el ordenamiento.
2.7 Isomorfismo de árboles

Objetivo de la unidad...
•El estudiante representará la estructura árbol
utilizando los tipos yrecorridos.
NON-ACTIVATED VERSION
www.avs4you.com

Definición...
•Es una estructura de datos ampliamente
usada que imita la forma de un árbol (un
conjunto de nodos conectados).
NON-ACTIVATEDVERSION
www.avs4you.com

Definición formal...
•Formalmente, podemos definir un árbol de la siguiente forma:
•* Caso base: un árbol con sólo un nodo (es a la vez raíz del árbol y
hoja).
•* Unnuevo árbol a partir de un nodo nr y k árboles A1, A2... Ak de
NON-ACTIVATED VERSION
raíces n1, n2,... nk con N1, N2,... Nk elementos cada uno, puede
www.avs4you.com
construirse estableciendo unarelación padre-hijo entre nr y cada una de
las raíces de los k árboles. A cada uno de los árboles Ai se les denota
ahora subárboles de la raíz.

Terminología y caracterización...
•Un nodo es launidad sobre la que se
construye el árbol y puede tener cero o
más nodos hijos conectados a él.
•Se dice que un nodo a es padre de un
nodo b si existe un enlace desde a hasta
b (en ese caso,también decimos que b
es hijo de a).

NON-ACTIVATED VERSION
www.avs4you.com un único nodo sin
•Sólo puede haber
padres, que llamaremos raíz.

• Un nodo que no tiene hijos se conoce
como hoja.
• Losdemás nodos (tienen padre y uno o
varios hijos) se les conoce como rama.

Tipos de árboles...
•Árboles Binarios
•Árbol de búsqueda binario auto-balanceable
•Árboles AVL

NON-ACTIVATED...