arboles

Estructuras de Datos

Mediante paréntesis anidados:

Árboles
Un árbol es una estructura jerárquica, organizada y
dinámica aplicada sobre una colección de objetos llamados
nodos.




Jerárquica porque los componentes están a distinto nivel.
Organizada porque importa la forma en que este dispuesto
el contenido.
Dinámica porque su forma, tamaño y contenido pueden
variar durante laejecución.

Los árboles genealógicos y los organigramas son
ejemplos comunes de árboles. Entre otras cosas, los árboles son
útiles para analizar circuitos eléctricos, para representar la
estructura de fórmulas matemáticas, para organizar información
en una base de datos, para representar el sistema de archivos y
para analizar la estructura sintáctica de un programa fuente en
loscompiladores.
Existen diferentes formas de representación de un árbol,
entre las más comunes se tienen las siguientes:
Mediante círculos y flechas:

Mediante notación decimal de Dewey:
1a, 1.1b, 1.1.1e, 1.1.2f, 1.2c, 1.3d
Identado, mediante nodos. Un buen ejemplo de esto, es la
forma de representar gráficamente las carpetas (directorios) de
un sistema de archivos. En este caso, una carpeta es unnodo
padre de los archivos y subcarpetas contenidas en él.
1. a
a. b
i. e
ii. f
b. c
c. d
La forma de representación más fácil, común es la
representación mediante círculos y flechas.

a

e

Conceptos básicos

c

b

MC Beatriz Beltrán Martínez

( a ( b (e, f), c, d ))

Definición: Un árbol se puede definir recursívamente como
sigue:
Un solo nodo es, por sí mismo, unárbol. Ese nodo es
también la raíz de dicho árbol.

d

f

1

Estructuras de Datos

Supóngase que r es un nodo y que A1, A2, n..., An son
árboles con raíces r1, r2, ...rn, respectivamente. Se puede
construir un nuevo árbol diciendo que r se constituya en
el padre de los nodos r1, r2, ...rn. Por lo que, en dicho árbol,
r será ahora la raíz y A1, A2, ...An serán los subárboles de
r. Losnodos r1, r2, ...rn serán ahora también hijos del
nodo r.

número n > 2 (llamado la aridad del árbol), entonces el árbol de
aridad n es llamado n-ario.

A

r

B

F
A1

A2

E

D

M

H

I

J

An

Algunas veces se incluye entre los árboles el árbol nulo
vacío, el cual, es un árbol sin nodos que se representa mediante
la letra .
Generalmente, se crea una relación oparentesco entre
los nodos de un árbol que impone una estructura jerárquica y
que da lugar a términos como padre, hijo, hermano, antecesor,
sucesor, etc. Se dice que la raíz de cada subárbol Ak es un hijo
de r y que r es el padre de cada raíz de los subárboles. En
principio cualquier nodo del árbol podría tener un número
arbitrario de nodos hijos, a esto se le conoce como un árbol
general,como se muestra en la siguiente figura. Si se limita el
número de nodos hijos para cada nodo del árbol, digamos a un

K






L

El nodo A es la raíz (padre).
Los hijos de A son B, C, D, E
Los nodos F, G, M son hermanos e hijos de B
A es abuelo de H
K y L son hijos de H y nietos de A

Con estas consideraciones se pueden definir las
siguientes características y propiedades delos árboles. Algunos
de los siguientes conceptos; sin embargo, no son uniformes en
toda la literatura referente a la teoría de árboles.


MC Beatriz Beltrán Martínez

G

C

Si hay un camino de A hasta B, se dice que A es
antecesor de B, y que B es sucesor de A.

2

Estructuras de Datos





















Padre es el antecesor inmediato de unnodo
Hijo, cualquiera de sus descendientes inmediatos.
Antepasado de un nodo, es cualquier antecesor de dicho
nodo.
Descendiente de un nodo, es cualquier sucesor de dicho
nodo.
Hermano de un nodo, es otro nodo con el mismo padre.
Raíz es el nodo que no tiene ningún predecesor.
Hoja (o nodo terminal) es el nodo que no tiene
sucesores.
Los nodos que tienen predecesor y sucesor se...