Arboles Generales

ÁRBOLES GENERALES (N-ARIOS)
Un árbol es un tipo especial de relación que es muy útil
para el estudio de una gran variedad de aplicaciones en las
ciencias de la computación e ingeniería. Un árbol se
representa como un grafo dirigido o no dirigido. Los
árboles son muy usados en el estudio y construcción de
base de datos, modelamiento jerárquico de clases y en la
teoría de lenguajes yconstrucción de compiladores, son
muy usados para describir los árboles sintácticos
correspondientes a gramáticas de lenguajes.

ÁRBOLES GENERALES (N-ARIOS)
Definición
Un árbol A se define como un conjunto de elementos
llamados nodos o vértices, de forma que:
- A es vacío, en cuyo caso se llama árbol vacío o árbol
nulo, o
- A contiene un nodo distinguido v0 llamado raíz de A y
los nodosrestantes de A forman un conjunto de árboles
A1, A2 , A3, ..., An
Cada árbol Ai tiene como raíz al nodo vi
Un árbol se representa mediante un grafo en donde la raíz
v0 es el nodo en A en la parte superior. Una línea hacia
abajo de izquierda a derecha, un arco señala a los hijos de
v0

ÁRBOLES GENERALES (N-ARIOS)
v0

v1

v2

v3

vn

A1

A2

A3

An

- A1, A2 , A3, ..., An sonllamados subárboles de v0
- Si Ai no es vacío, entonces su raíz vi, es llamado hijo de
v0, y v0 es llamado padre de vi

ÁRBOLES GENERALES (N-ARIOS)
ÁRBOLES LIBRES Y ÁRBOLES CON RAIZ
Un árbol libre es un tipo especial de grafo no dirigido,
cualquiera de sus nodos puede ser considerado una raíz.
Un árbol con raíz es un tipo especial de grafo dirigido. Es
un árbol con única raíz.
Ejemplosde árboles libres:

ÁRBOLES GENERALES (N-ARIOS)
Ejemplos de árboles con raíz:

ÁRBOLES GENERALES (N-ARIOS)
Definición
Sea V: conjunto de vértices o nodos
A: relación: aristas o caminos entre los elementos de
V
(A, v0) es un árbol si y solo si:
1. Existe un único vértice v0 ∈ V tal que v0 no tiene
ninguna entrada. v0 es llamado raíz del árbol A.
2. ∀ v ∈V tal que v ≠ v0, v tiene solouna entrada.

ÁRBOLES GENERALES (N-ARIOS)
Si (A, v0) es un árbol
1. A es una relación irreflexiva (no existen ciclos).
2. A es asimétrica, si u es padre de v, v no puede ser
padre de u.
3. Si a R b y b R c entonces a ¬R c ∀ a,b,c ∈ V
R no es transitiva. Es decir si a es padre de b, y b es
padre de c, no es cierto que a es padre de c.

ÁRBOLES GENERALES (N-ARIOS)
Definición recursivade árbol
Un árbol A es un conjunto de nodos V, donde
Si V = vacío A es el árbol nulo
Si V ≠ vacío
Existe v0 ∈ V llamado raíz de A
y existen A1, A2 ,..., An, con raíces v1, v2 ,..., vn
respectivamente tal que existe una arista (v0, vi) ∀i
Cada Ai es un subárbol del árbol A
1. Un vértice es por si mismo un árbol, este nodo es la
raíz de dicho árbol.
2. La raíz del árbol Ai es vi
vi esllamado hijo de v0

ÁRBOLES GENERALES

v0

A1
v1

A2
v2

An
vn

ÁRBOLES GENERALES (N-ARIOS)
Niveles jerárquicos de un árbol
Cada nodo de un árbol A tiene asignado un número de
nivel. La raíz de A tiene asignado el nivel 0. Los demás
nodos de A tienen asignado un número de nivel que es
mayor en 1 al número de nivel de su padre.
Los nodos del mismo nivel se dicen hermanos.Terminología Fundamental
Sea n1, n2 ,..., nk secuencia de vértices o nodos tal que ni es
el padre de ni+1, para todo i de 1 a k
- Denominamos raíz al único nodo que no tiene padre,
que corresponde al nodo de nivel 0.
- Denominamos hoja (o terminal) a los nodos que no
tienen hijos.

ÁRBOLES GENERALES (N-ARIOS)
- La secuencia de nodos (n1, n2 ,..., nk) se denomina
camino del nodo n1, al nodonk
- La longitud de camino es el número de nodos de la
secuencia menos uno. La longitud de camino está
determinado por el número de aristas del camino, no por
el número de nodos del camino. Así el camino (a,b,c) es
de longitud 2, el camino (a, b) es de longitud 1, el camino
(a) es de longitud 0.
- El camino de un nodo hacia si mismo es de longitud 0.
- Si existe un camino del nodo a...