arbol

Algoritmos II

Estructuras Jerárquicas

Tema 3

Estructuras Jerárquicas
Árboles

1. Introducción
Algunas veces, cuando se modela una situación, se determina que la mejor manera de representar la relación
que existe entre los objetos involucrados es mediante una estructura jerárquica. Algunos ejemplos típicos de
esta situación son los siguientes:
a) Organigrama: Describe laorganización administrativa (estructura) de una empresa a través de la relación
entre las diferentes unidades de trabajo.
b) Índice de un libro: Enumeración ordenada del contenido de un libro.
c) Árboles genealógicos: Representación gráfica de los ancestros y descendientes de una persona.
En estos casos se necesita una estructura adecuada que permita representar este tipo de estructuras
jerárquicas, losárboles.

2. Árboles: Definiciones Básicas
a) Árbol: Un árbol es un grafo conexo y acíclico.
b) Grado de un nodo: En los grafos no dirigidos es el número de arcos que inciden sobre un vértice. En los
grafos dirigidos existen dos tipos de grado: (1) Grado de entrada, el cual es la cantidad de arcos que inciden
positivamente sobre un vértice (gráficamente son las flechas que llegan), y (2)Grado de salida, el cual es la
cantidad de arcos que inciden negativamente sobre un vértice (gráficamente son las flechas que salen).
(Nota: En este tema cuando se hable del grado de salida de un nodo se le llamará simplemente grado, y
representará el número de hijos (subárboles) de ese nodo.)
c) Grado de un árbol: Es el grado del nodo de mayor grado en el árbol.
d) Peso de un árbol: Es elnúmero de nodos que contiene el árbol. El peso de un árbol nulo es 0.
e) Nodo terminal u hoja: Es un nodo de grado 0.
f) Nodo no terminal o interior: Es todo nodo de un árbol que no es una hoja.
g) Nodos hermanos: Dos nodos e1 y e2 de un árbol son hermanos si y sólo si tienen el mismo padre.
h) Camino entre dos nodos: Un camino entre dos nodos e y e' de un árbol es una secuencia de nodos
tal queverifica las siguientes propiedades:
• e1 = e
• en = e'
• ∀i ( 1 ≤ i < n ): ei es padre de ei+1.

Universidad de Carabobo

Facultad Experimental de Ciencias y Tecnología

Departamento de Computación
Pág. 1

Algoritmos II

i)

j)

Estructuras Jerárquicas

Longitud de un camino: La longitud de un camino C = se define como el número de veces
que se debe aplicar la relaciónpadre → hijo durante el recorrido, es decir, es el número de arcos en el
camino o el número de nodos en el camino menos 1.
Rama: Es un camino que parte de la raíz y termina en una hoja.

Nodo Raíz
Grado = 3
Rama
Longitud = 3

Nodo Interior
Grado = 2
Nodo Hoja
Grado = 0
Camino
Longitud = 1
Grado del Árbol = 3
Peso del Árbol = 13

Nodos Hermanos
Figura 1. Algunos conceptos básicos deun árbol.

k) Nivel de un nodo: Es la longitud del camino que parte de la raíz y llega a ese nodo.
l) Altura de un nodo: Es la longitud del camino más largo desde el nodo hasta una hoja.
m) Altura de un árbol: Es la altura de la raíz del árbol. La altura de un árbol nulo se define como -1.

Nivel 0

Nivel = 2

Nivel 1

Nivel 2
Altura = 1
Nivel 3
Altura del Árbol = 3
Figura 2. Nively altura de un nodo. Altura de un árbol.

Universidad de Carabobo

Facultad Experimental de Ciencias y Tecnología

Departamento de Computación
Pág. 2

Algoritmos II

Estructuras Jerárquicas

3. Árboles N-Arios
Formalmente, un árbol n-ario no ordenado con tipo base T se puede definir de manera recursiva como sigue:
a) La secuencia vacía representa al árbol nulo no ordenado. Sedenota por Λ.
b) Sea e un elemento de tipo T y A1, A2, …, An árboles n-arios no ordenados con tipo base T. Entonces la
secuencia A = , donde [A1, A2, …, An] denota un multiconjunto de árboles n-arios, es un
árbol n-ario no ordenado con tipo base T y se definen las siguientes relaciones:
• e es la raíz de A.
• ∀i ( 1 ≤ i ≤ n ): Ai es un subárbol de A.
• ∀i ( 1 ≤ i ≤ n ): e es padre de la raíz...