algoritmo

Unidad 2: Estructuras de Datos
Tema IV. Estructuras de Datos
compuestos enlazados
Segunda Parte: Árboles binarios. Árbol
binario de búsqueda.
Grafos. Buscando el camino entre dos
vértices del grafo.

Prof. ADJ. (ord) Vallejos, Oscar Adolfo - Fa.Ce.Na.

Árboles
Los árboles constituyen estructuras de datos jerarquizados, y
tienen multitud de aplicaciones.
Análisis de circuitos,Representación de estructuras de
fórmulas matemáticas
Organización de datos en bases de datos
Representación
compiladores.

de

la

estructura

sintáctica

en

En muchas otras áreas de las ciencias del computador.
Un árbol está constituido por una colección de elementos
denominados nodos, uno de los cuales se distingue con el nombre
de raíz, junto con una relación de 'parentesco' queestablece una
estructura jerárquica sobre los nodos.
Cada nodo tiene un padre (excepto el raíz) y puede tener cero o
más hijos.
Se denomina hoja a un nodo sin hijos.

Árboles
Un árbol es una estructura de datos jerarquizada aplicada sobre una
colección de elementos u objetos (nodos). Que se puede definir en forma
recursiva. (Una estructura vacía o un elemento o clave de información(nodo) más
un número finito de estructuras tipo árbol, disjuntos, llamados subárboles. Si dicho
número de estructuras es inferior o igual a 2, se tiene un árbol binario. Es, por
tanto, una estructura no secuencial).
Cada dato reside en un nodo, y existen relaciones de parentesco entre
nodos.

Prof. Oscar Adolfo Vallejos

Otra definición nos da el árbol como un tipo de grafo
Un árbol es ungrafo acíclico, conexo y no dirigido. Es
decir, es un grafo no dirigido en el que existe
exactamente un camino entre todo par de nodos.
Esta definición permite implementar un árbol y sus
operaciones empleando las representaciones que se
utilizan para los grafos.

Terminologías

Árboles
A

Todo árbol que no es vació, tiene un único nodo
raíz.
Un nodo “B” es descendiente directo de unnodo
“A”, si el nodo “B” es apuntado por el nodo “A”. “B”
es hijo de “A”.

B

C

Un nodo “A” es antecesor directo de un nodo “B”, si
el nodo “A” apunta al nodo “B”. “A” es padre de
“B”.
Los
nodos
son
hermanos
cuando
son
descendientes directos de un mismo nodo. Hijos de
un mismo padre. (B y C).

F
D

E

Un nodo es interior cuando no es raíz ni hoja. (F).
Se conoce con elnombre de “grado” al número de
descendientes directos de un determinado nodo. El
grado del árbol será entonces el máximo grado de
todos los nodos del árbol. (2).
Una colección de dos o mas árboles se llama
bosque.

G

H

Terminologías

Árboles

A

Todos los nodos tienen un solo padre a excepción del
nodo raíz (no tiene padre).
Todo nodo que no tiene descendientes directos(hijos),
se conoce con el nombre de terminal u hoja (D, E, G,
H)

B

C

Camino: Es el recorrido que enlaza nodos consecutivos.
(secuencia de nodos tales que cada uno es hijo del
anterior). (A , C, F).. Longitud del camino: nº de nodos
que tiene
Rama es el camino que termina en un hoja (C, F, H).
Cada nodo tiene asociado un numero de nivel que se
determina por la longitud del camino desde laraíz hasta
el nodo especificado. Por definición la raíz tiene nivel 1.
(F = 3).

F
D

E

Antecesor: un nodo es antecesor de otro si hay un
camino del primero al segundo
Descendiente: un nodo es descendiente de otro si hay
un camino del segundo al primero
Subárbol o Rama: Un nodo y todos sus descendientes

G

H

Árboles - Definición recursiva de los árboles
Un nodo simple nconstituye un árbol.
Se denomina la raíz del árbol
Supongamos que n es un nodo y T1, T2, ..., Tk son árboles cuyas
raíces son n1, n2, ..., nk, respectivamente.
Podemos construir un nuevo árbol haciendo que n sea el padre de los
nodos n1, n2, ..., nk
En el nuevo árbol n es la raíz y n1, n2, ..., nk se denominan los hijos
de n
Los hermanos se ordenan generalmente de izquierda a derecha...