UNIDAD 6:

Contenedores No Lineales

Arboles
Terminología y Recorridos

Apuntes de apoyo para clases teóricas.

Para una conceptualización completa de los temas, los alumnos deberán asistir a las clases
teóricas y completar con lectura del material bibliográfico propuesto.

8/4/2023 1
 Bibliografía :
1. Hibbard, Thomas N y Yazlle, Jorge F. EUNSA. (2015) Matemática Discreta.

2. Aho, Hopcroft y Ullman. Addison Wesley. (1988). Estructuras de Datos y Algoritmos.

3. Brassard, Gilles; Bratley, Paul. PRENTICE HALL (1997). Fundamentos de Algoritmia..

4. Kolman - Ross-Wrigth , Estructuras de Matemática Discreta para la Computación. Cap 4

y 6.

5. D. E. Knuth. Ed. Reverté – Reimpresión Año 2002. El arte de programar ordenadores.

Clasificación y Búsquedas. Volúmen III . Pag. 462.
6. Richard Johnsonbaugh. Prentice Hall .Edición – Año 1997.Matemáticas Discretas

7. C. L. Liu - Mc Graw Hill – 2dta. Edición – Año 1995. Elementos de Matemática Discreta

8. Software de visualización de algoritmos : Gnarley Trees (Universidad de Eslovaquia)

2
 Autor: Jakub (kuko) Kováč , Comenius Universit, Bratislava, Eslovaquia
Octubre de 2013 a la fecha : Software Engineer en Facebook Inc., Londres
8/4/2023 3
 Campo de Aplicación de los Arboles
➢ Evaluadores de expresiones aritméticas, geometría computacional,
sistemas operativos (Ciencias de la computación)

➢ Representaciones de jerarquía entre sus elementos:

❑ Organigramas
❑ Árboles genealógicos
❑ Tabla de contenidos
❑ Árboles de decisión con dos opciones, también pueden ser de 3
opciones.
❑ Juegos de algún campeonato
❑ Representación de expresiones que contienen operandos y
operadores binarios.

8/4/2023 4
 ➢ Objetivos de esta parte:

➢ Generales (A)
➢ Preorden
➢ Arboles
➢ Binarios (AB) ➢ Recorridos ➢ Inorden
➢ Posorden

8/4/2023
 Arbol General: Definición I
Sea G = (N, A, P), donde
➢ N, es un conjunto de nodos
➢ A, es un conjunto de aristas
➢ P, es una función de las aristas, tal que cada P(a) = {p, q}

El grafo G es un árbol, si G es conexo y NO contiene ciclos.

Ej.: Ya vimos el árbol cubridor, también podemos representar jerarquías, etc.

a) u v b) Libro: Libro
C1
S1.1
S1.2 C1 C2 C3
w C2
x
C3
S3.1 S1.1 S1.2 S3.1 S3.2 S3.3
y S3.2
S3.2.1
z S3.2.2
S3.2.1 S3.2.2
S3.3
8/4/2023 6
 Arbol General: Definición II
Un ARBOL es un conjunto finito de uno o más nodos, tales que:

• Existe un nodo especial llamado raíz del árbol (V1)

• Los nodos restantes (v2,v3,..,vn) se dividen en m>=0 conjuntos disjuntos

denominados T1, T2,....Tm , cada uno de los cuales es a su vez, un árbol. Estos se
llaman subárboles de la raíz.

•Un árbol con 0 nodos es el árbol vacío

Ejemplo: m= 3 V1

V1 V5 V6

V9 V10 V11 V12

V7 V8

T1 T2 T3
8/4/2023 7
 Arboles Binarios (AB) :Definición
Los árboles binarios son los tipos particulares más importantes de árboles generales con
raíz:

• Cada nodo tiene cero, uno o dos subárboles ó hijos. (0  m  2)

• Cada nodo de un árbol binario tiene a lo sumo dos subárboles.

• Cada subárbol se designa como hijo izquierdo o hijo derecho.

A x Nodo raíz

I D
y z

Hijo izquierdo Hijo derecho

u v

8/4/2023 8
 Arboles Binarios (AB) …
Relaciones de parentesco y conceptos asociados con la teoría de árboles.
➢ Raíz: Nodo “x”

➢ Subárbol izquierdo de A: I
A x ➢ Subárbol derecho de A: D

I D ➢ Nodo “x” es padre de los nodos “y” y “z”

y z ➢ Nodos “y” y “z”, son hijos del nodo “x”

➢ Nodo “x” es ancestro de los nodos “y” y “z”

u v ➢ Nodos “y” y “z”, son descendientes del nodo “x”

➢ Nodos hojas o terminales: Son aquellos que no

tienen hijos o descendientes. Por ejemplo, los
Notación:
nodos “u”, “v” y “z”.
(x, (y, (u, Ø, Ø), (v, Ø, Ø)) , (z, Ø, Ø))
➢ El grado de cada nodo puede ser 1, 2 o 3.
8/4/2023 9
 Arboles Binarios (AB): Nivel - Altura
Nivel a = Altura = Nivel + 1 ❑ Al nivel 1 pertenecen los
0 15 1 nodos con valores 10 y 30, se
A
dice que pertenecen a la
misma generación.
1 I 2
10 30
❑ Altura de A es 4. Nos dá una
idea de la cantidad de
2 3 búsquedas que se deben
7 12 21
realizar para encontrar o no
un elemento dado.
3 4
11 25 ❑ Altura de I, es igual a 3.

Nivel de un vértice o nodo, es la longitud de camino ❑ Altura de (12, (11, Ø, Ø), Ø),
simple a la raíz. es igual a 2.
La profundidad o altura de un árbol A, es el número
máximo de nivel que aparece en dicho árbol más 1.
8/4/2023 10
 Arboles Binarios (AB):

❑ Recorridos de un árbol:
A 15
❑ Preorden
❑ Inorden
10 30
❑ Posorden

7 12 21

11 25

11
 Arboles Binarios (AB): Recorrido
PREorden
A
15

10 30

7 12 21

11 25

Preorden(A) =15,10,7,12,11,30,21,25

8/4/2023 12
 Arboles Binarios (AB): Recorridos
A 15
Dado un Arbol Binario de raiz A:
a) preorden:
1° procesar la raíz A
10 30
2° recorrer el subárbol izquierdo de A en preorden
3° recorrer el subárbol derecho de A en preorden

A = (15, (10, (7, Ø, Ø), (12, (11, Ø, Ø), Ø) ), (30, (21, Ø, (25, Ø, Ø) ), Ø ) ) 7 12 21

preorden((15, (10, (7, Ø, Ø), (12, (11, Ø, Ø), Ø) ), (30, (21, Ø, (25, Ø, Ø) ), Ø ) ) ):
Procesar la raíz (ese proceso puede ser mostrar el valor de la raíz) // 15
preorden((10, (7, Ø, Ø), (12, (11, Ø, Ø), Ø) )) (1) 11 25

(1) preorden( (10, (7, Ø, Ø), (12, (11, Ø, Ø), Ø) )):

Procesar la raíz // 10
preorden( (7, Ø, Ø) ) (3)
preorden( (12, (11, Ø, Ø), Ø) ) (4) Diapositiva siguiente

(3) preorden( (7, Ø, Ø) ):

Procesar la raíz // 7
preorden( (Ø) ) (5)
preorden( (Ø) ) (6)

(5) preorden( (Ø) ): Fin de la llamada recursiva 5

(6) preorden( (Ø) ) : Fin de la llamada recursiva 6 13
 Arboles Binarios (AB): Recorridos
A 15
Dado un Arbol Binario de raiz A:
a) preorden:
1° procesar la raíz A
10 30
2° recorrer el subárbol izquierdo de A en preorden
3° recorrer el subárbol derecho de A en preorden

A = (15, (10, (7, Ø, Ø), (12, (11, Ø, Ø), Ø) ), (30, (21, Ø, (25, Ø, Ø) ), Ø ) ) 7 12 21

preorden((15, (10, (7, Ø, Ø), (12, (11, Ø, Ø), Ø) ), (30, (21, Ø, (25, Ø, Ø) ), Ø ) ) ):
Procesar la raíz // 15
preorden((10, (7, Ø, Ø), (12, (11, Ø, Ø), Ø) )) (1) 11 25
preorden((30, (21, Ø, (25, Ø, Ø) ), Ø ) ) (2) (Diapositiva siguiente)
(1) preorden( (10, (7, Ø, Ø), (12, (11, Ø, Ø), Ø) )):
Procesar la raíz // 10
preorden( (7, Ø, Ø) )
preorden( (12, (11, Ø, Ø), Ø) ) (4)

(4) preorden ( (12, (11, Ø, Ø), Ø) ) :

Procesar la raíz // 12
preorden((11, Ø, Ø) ) (7)
preorden( (Ø) ) (8)
(7) preorden((11, Ø, Ø)):
Procesa la raíz //muestra 11
preorden((Ø): Fin de la llamada recursiva
preorden((Ø): Fin de la llamada recursiva
14
(8) preorden( (Ø) ) : Fin de la llamada recursiva 8
 Arboles Binarios (AB): Recorridos
A 15
Dado un Arbol Binario de raiz A:
a) preorden:
1° procesar la raíz A
10 30
2° recorrer el subárbol izquierdo de A en preorden
3° recorrer el subárbol derecho de A en preorden

A = (15, (10, (7, Ø, Ø), (12, (11, Ø, Ø), Ø) ), (30, (21, Ø, (25, Ø, Ø) ), Ø ) ) 7 12 21

preorden((15, (10, (7, Ø, Ø), (12, (11, Ø, Ø), Ø) ), (30, (21, Ø, (25, Ø, Ø) ), Ø ) ) ):
Procesar la raíz // 15
preorden((10, (7, Ø, Ø), (12, (11, Ø, Ø), Ø) )) 11 25
preorden((30, (21, Ø, (25, Ø, Ø) ), Ø ) ) (2)
(2) preorden((30, (21, Ø, (25, Ø, Ø) ), Ø )):
Procesar la raíz // 30
preorden( (21, Ø, (25, Ø, Ø) ) ) (9) Preorden(A) =15,10,7,12,11,30,21,25
preorden( (Ø) ) (12)

(9) preorden ( (21, Ø, (25, Ø, Ø) ) ) :

Procesar la raíz // 21
preorden( (Ø) ) (10): Fin de la llamada recursiva 10
preorden((25, Ø, Ø) ) (11)
(11) preorden((25, Ø, Ø)):
Procesa la raíz //muestra 25
preorden((Ø): Fin de la llamada recursiva
preorden((Ø): Fin de la llamada recursiva
(12) preorden( (Ø) ) : Fin de la llamada recursiva 12
 Arboles Binarios (AB): Recorrido
INorden
A
15

10 30

7 12 21

11 25

inorden(A) = 7,10,11,12,15,21,25,30

8/4/2023 16
 Arboles Binarios (AB): Recorridos
Dado un Arbol Binario de raiz A: A 15
b) inorden:
1° recorrer el subárbol izquierdo de A en inorden
2° procesar la raíz A
10 30
3° recorrer el subárbol derecho de A en inorden

Prueban los alumnos:

 inorden(A) = 7,10,11,12,15,21,25,30 7 12 21

11 25

8/4/2023
17
 Arboles Binarios (AB): Recorrido
POSorden
15

10 30

7 12 21

11 25

posorden(A) = 7,11,12,10,25,21,30,15

8/4/2023 18
 Arboles Binarios (AB): Recorridos
A 15
Dado un Arbol Binario de raiz A:
c) posorden:
1° recorrer el subárbol izquierdo de A en posorden
10 30
2° recorrer el subárbol derecho de A en posorden
3° procesar la raíz A

7 12 21
Prueban los alumnos:
 posorden(A) = 7,11,12,10,25,21,30,15

11 25

8/4/2023 19
 Vimos aquí

➢ Generales (A)
➢ Preorden
➢ Arboles
➢ Binarios (AB) ➢ Recorridos ➢ Inorden
➢ Posorden

8/4/2023 20