Módulo 1

ÁR B OLES

Introducción

1. ÁR B OLES

1.1 Concepto de árbol

1.2 ¿Cómo de nimos un nodo?

1.3 Propiedades de un árbol

1.4 Nodos hermanos

1.5 Árbol binario

1.6 ¿Cómo crear nodos?

CIER R E DEL MÓDULO

Descarga del contenido

18

Introducción

Verify to continue
We detected a high number of errors from your
connection. To continue, please confirm that
you’re a human (and not a spambot).

I'm not a robot

reCAPTCHA
Privacy - Terms

En este módulo veremos cómo almacenar datos en forma ordenada, para la representación de
expresiones aritméticas, dado que una, con dos operandos, la podemos representar como un árbol cuya
raíz sea el operador y sus subárboles sean los operandos. Por tal motivo, crear un mal funcionamiento
del algoritmo puede borrar información equivocada o generar un desbordamiento de datos básicos.
Objetivos del módulo

Resolver problemas complejos entendiendo las estructuras de datos y avanzando en los saberes
previos a través de la programación orientada a objetos.

Seleccionar las herramientas adecuadas.

Elaborar documentación pertinente.

Implementar y evaluar la solución desarrollada.

 1.1. Concepto de árbol.
1.2. ¿Cómo definimos un
nodo?
UNIDAD 1 1.3. Propiedades de un
Árboles árbol.
1.4. Nodos hermanos.
1.5. Árbol binario.
1.6. ¿Cómo crear nodos?

C O NT I NU A R
28

1.1 Concepto de árbol

En esta unidad abordaremos el concepto de árbol, sus características y utilizaciones. También veremos los
alcances de esta estructura no lineal, acompañados de ejemplos para su mejor comprensión.

Es importante tener en cuenta que las estructuras de datos, así como arreglos y registros son estáticas,
mientras que las listas y los árboles son dinámicas.

Es una estructura de datos no lineal, hasta ahora se vieron colas, pilas y listas. Estas eran estructuras de
datos lineales; ya que al tener un puntero siguiente podíamos recorrer la lista de una sola forma. En cambio,
en el árbol, no tendremos un puntero, sino, dos: uno para la derecha y otro para la izquierda. Es decir,
podremos recorrer el árbol de diferentes formas. Es por ello que, a los árboles, se los conoce como
estructuras dinámicas y no lineales.

Estos árboles consisten en un conjunto de nodos y aristas, de forma que:

Se distingue un nodo llamado raíz.

A cada nodo “H”, excepto la raíz, le llega una arista de otro nodo (“P” padre de “H” y “H”, uno de
los hijos de “P”).

A su vez, el conjunto finito de líneas, que conectan los nodos, son lo que se denomina como ramas.

Características

1 Todo árbol que no es vacío tiene un único nodo raíz.

2 Un nodo X es descendiente directo de un nodo Y, si el nodo X es apuntado por el nodo Y. En

este caso es común utilizar la expresión X es hijo de Y.

3 Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al nodo Y. En este caso es

común utilizar la expresión X es padre de Y.

4 Se dice que todos los nodos que son descendientes directos de un mismo nodo (padre), son
hermanos.

5 Todo nodo que no tiene ramificaciones (hijos) se le conoce con el nombre de terminal u hoja.

6 Todo nodo que no es raíz, ni terminal u hoja, se conoce con el nombre de interior.

7 Grado de un nodo es el número de descendientes directos de un determinado nodo. Grado del

árbol es el máximo grado de todos los nodos del árbol.
8 Nivel o profundidad de un nodo es el número de arcos que deben ser recorridos para llegar a un
determinado nodo. Por definición la raíz tiene nivel 1.

9 La altura de un árbol es la profundidad del nodo más profundo.

Teniendo en cuenta estas características, construyamos nuestro primer nodo con el nombre A,
denominado raíz.

Figura 1. Raíz. Elaborada a partir de Ingeniería de Software (s/f).

Este primer nodo puede tener hijos, tanto a la derecha como a la izquierda. Por ende, los nodos que
derivan de la raíz, se denominan hijos.

Figura 2. Raíz y nodo hijo. Elaborada a partir de Ingeniería de Software (s/f).

Estos nodos hijos, también pueden tener otros hijos denominados, como los anteriores, nodos hijos.

Figura 3. Nodos y nodos hijos. Elaborada a partir de Ingeniería de Software (s/f).

 La particularidad de D, E y F, es que no poseen hijos y, por eso mismo, son denominados “hojas”.

Figura 4. Hojas. Elaborada a partir de Ingeniería de Software (s/f).

Ya hemos visto qué se entiende por raíz, nodo hijo y hoja. Ahora, observemos cómo se ve esto en un árbol
con números enteros:
 Figura 5. Árbol. Elaboración propia.

El 16 es la raíz, el 8 y el 24 son los nodos hijo y el 7, 13 y 21 son las hojas porque ya no tienen hijos.

Estructuras de datos

La siguiente imagen les permitirá observar el alcance de lo que venimos viendo a lo largo del módulo y hacia
dónde apuntamos en la programación.

LINEALES
Figura 1. Estructuras de datos lineales y no lineales. Elaboración propia.

C O NT I NU A R
38

1.2 ¿Cómo definimos un nodo?

Para definir una estructura nodo necesitamos un nodo que apunte a otros nodos. En la figura 6, definimos
una estructura de este tipo con tres campos.

Figura 6. Estructura nodo. Elaborada a partir de Ingeniería de Software (s/f).

En el primero de ellos, colocamos un dato que es del tipo entero (el n° 16) y es lo que se denomina como raíz.
Puede apuntar tanto a la derecha como a la izquierda. Por tal motivo, necesitamos dos punteros, uno para
cada lado. En este caso lo usamos para un árbol binario, pero si fuese para un árbol ternario que tenga tres o
más hijos, necesitaríamos más punteros.

C O NT I NU A R
48

1.3 Propiedades de un árbol

Los árboles presentan determinadas propiedades. A continuación, veremos qué implica cada una de ellas.

Longitud de camino:
Es el número de ramas que uno tiene que pasar para llegar de un nodo a otro, generalmente se comienza del
nodo raíz. Por ejemplo: si queremos saber la longitud de camino del nodo 7, debemos contar la cantidad de
ramas. Es decir, cada una de las líneas o flechas desde la raíz hasta el número 7 (ver Figura 7). En este caso,
la longitud de camino para encontrar el nodo 7, es 3.

Figura 7. Longitud de camino. Elaboración propia.

Otra forma de calcular esto, es contando el número de nodos menos 1. Aquí no debemos contar las ramas
y/o flechas sino los nodos. Por ejemplo: desde la raíz y hasta el 7, inclusive, hay 4 nodos. Le restamos 1 a 4 y
nos da 3 (ver Figura 8).

Figura 8. Longitud de camino del nodo. Elaboración propia.

Altura de un nodo:
Si queremos calcular la altura del nodo 24, debemos observar desde las hojas y hacia arriba. En este caso,
la altura es 2 (ver Figura 9).
 Figura 9. Altura de un nodo. Elaboración propia.

Profundidad de un nodo:
La profundidad se ve desde arriba. Es decir, desde la raíz y hacia abajo. Por lo tanto, para hallar la
profundidad de un nodo, debemos tener en cuenta los niveles. Por ejemplo: en la figura 10, la raíz es el nivel 0
del árbol y profundidad del nodo 19 es igual a 2; ya que se encuentra en dicho nivel.
Figura 10. Profundidad de un nodo. Elaboración propia.

C O NT I NU A R
58

1.4 Nodos hermanos

Se caracterizan por estar al mismo nivel y, además, tener en común el mismo padre. Por ejemplo: en la
figura 11, los nodos hermanos son el 3 y el 13 o el 8 y el 24; ya que son hijos del 8, respectivamente. Si bien
el 13 y el 19, comparten la misma línea, no comparten el mismo padre.

Figura 11. Nodos hermanos. Elaboración propia.

Por otro lado, el orden un árbol será la máxima cantidad de hijos que puede tener cada nodo. Por ejemplo: si
un árbol es del orden 2, esto significa que puede tener 0, 1 o 2 hijos. Este tipo de árbol es conocido como
binario.

C O NT I NU A R
68

1.5 Árbol binario

Un árbol binario es un árbol de orden 2. Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la
derecha como hijo derecho.

Un árbol ordenado es aquel en el que las ramas de los nodos del árbol están ordenadas. Teniendo en cuenta
esto, podemos decir que un árbol binario es un árbol ordenando que puede tener cuando máximo dos
subárboles denominados: subárbol izquierdo y subárbol derecho. Este tipo de árbol, presenta las siguientes
características:

Si A es la raíz de un árbol y B es la raíz de su subárbol izquierdo (o derecho), se dice que A es el

padre de B y se dice que B es el hijo izquierdo de A.

Un nodo que no tiene hijos, se denomina hoja.

El nodo A es antecesor del nodo B (y recíprocamente el nodo B es descendiente del nodo A), si
A es el padre de B o el padre de algún ancestro de B.

Un nodo B es un descendiente izquierdo del nodo A, si B es el hijo izquierdo de A o un

descendiente del hijo izquierdo de A. Un descendiente derecho se define de la misma forma.

Dos nodos son hermanos si son hijos izquierdos y derecho del mismo padre.

Un árbol binario es, además, una estructura recursiva y se divide en tres subconjuntos distintos:
 1 Nodo raíz.

2 Subárbol izquierdo.

3 Subárbol derecho.

En el árbol de la figura 12, tenemos tres partes: la raíz (indicado con la letra R), de allí, se desprende un
subárbol izquierdo (indicado con la letra I) y un subárbol derecho (indicado con la letra D).

Figura 12. Árbol. Elaboración propia.

Decimos que es recursivo porque si separamos la raíz, nos queda de la siguiente manera:
 Figura 13. Raíz y subárbol. Elaboración propia.

Si observamos la figura 13, podemos decir que el subárbol izquierdo es un árbol binario al igual que el
subárbol derecho.

Tipos de árbol binario

Árbol lleno
–
Todos sus nodos, salvo los últimos, tienen 2 hijos (ver Figura 14).

Figura 14. Árbol lleno. Elaborada a partir de Ingeniería de Software (s/f).

Árbol completo
–
Se lo denomina de esta forma porque los niveles no son completos. Generalmente, el subárbol izquierdo
está más completo que el subárbol derecho (ver Figura 15).

Figura 15. Árbol completo. Elaboración propia.

Árbol degenerado
–
Es un árbol en el que todos los nodos tienen solamente un subárbol excepto el último (figura 16).

Figura 16. Árbol degenerado. Elaboración propia.

Árbol binario de búsqueda (ABB)
–
Es aquel en el que, dado un nodo, todos los datos del subárbol izquierdo son menores y todos los datos del
subárbol derecho, son mayores. En la figura 17 se ingresan los datos teniendo en cuenta los siguientes
criterios:

Nuevo_nodo=5; (al ingresar este nodo, lo colocamos del lado izquierdo porque los numero menores,
en este caso 10, se colocan de ese lado).

Nuevo_nodo=15; (15 es mayor a 10, entonces lo colocamos del lado derecho).

Nuevo_nodo=4; (4 es menor a 10 y también menor a 5, por eso se coloca en el lado izquierdo).

Nuevo_nodo=8 (8 es menor a 10, por lo tanto, se coloca del lado izquierdo, pero es mayor que 5,
entonces, se coloca del lado derecho).

Nuevo_nodo=20 (20 es mayor a 10 y mayor a 15 y, por este motivo, lo colocamos del lado derecho).

Figura 17. ABB. Elaboración propia.

C O NT I NU A R
78

1.6 ¿Cómo crear nodos?

Primeramente, debemos crear un nodo con tres campos, tal como se observa en la figura 18. El primero es el
campo DATO y es donde se almacena el dato que queremos colocar. Este es del tipo entero y cuenta con un
puntero hacia el hijo derecho y otro hacia el hijo izquierdo. Luego, se crea el nodo como nuevo_nodo y se le
asignan los tres campos del nodo. Como el nodo derecho e izquierdo son nuevos, le asignamos NULL.

Figura 18. Creación de nodo. Elaborada a partir de Ingeniería de Software (s/f).

Es importante tener en cuenta ciertos aspectos al momento de insertar un árbol. Por ejemplo: el lado
izquierdo, nos indica si el nodo se encuentra vacío. En cambio, el lado derecho es para saber si tiene un nodo
o más de uno. Recordemos que los datos, dependiendo del valor que tengan, se colocan en el lado izquierdo
o derecho.
 Figura 19. Aspectos a tener en cuenta al insertar un nodo en el árbol. Elaborada a partir de
Ingeniería de Software (s/f).

En caso de crear un nuevo nodo en C++, deberíamos realizarlo tal como se muestra en las siguientes
imágenes.
 Figura 20. Creación de un nuevo nodo en C++ (Paszniuk, s/f).

En la línea 15 se crea el árbol y en la 13 se crea un nuevo nodo (ver Figura 21).

 Figura 21. Creación de un nuevo nodo y nuevo árbol en C++ (Paszniuk, s/f).

Figura 22. Función de menú e insertado de nuevo nodo en C++ (Paszniuk, s/f).
En la línea 40, podemos observar de manera detallada cómo debe ingresarse el nuevo nodo (ver Figura 23).

Figura 23. Insertado de nuevo nodo en C++ (Paszniuk, s/f).

A su vez, lo cargado en dicha línea se compila y aparece tal como se observa en la figura 24.
 Figura 24. Compilación de nuevo nodo en C++ (Paszniuk, s/f).

Para finalizar, debemos registrar los que se observa, en la figura 25, luego de la línea 40.

Figura 25. Función para insertar elementos en el árbol en C++ (Paszniuk, s/f).

La importancia de la programación

En este video podremos ver cuál es la importancia de la programación y cómo podemos aplicarla.

Verify to continue
We detected a high number of errors from your
connection. To continue, please confirm that you’re
a human (and not a spambot).

I'm not a robot

reCAPTCHA
Privacy - Terms
ADELS SCHOOL OF EDUCATION (19 de mayo de 2016). ¿Qué es la programación y para qué se utiliza? [Video]. Youtube

Marque la opción correcta. ¿Cómo se calcula la

profundidad de un nodo?

Partiendo desde abajo y hacia la raíz.

Partiendo del nodo que se encuentra más a la izquierda y

hacia el último nodo de la derecha.

Partiendo del nodo que se encuentra más a la derecha y

hacia el último nodo de la izquierda.

Partiendo desde la raíz y hacia abajo.

 SUBMIT

Bibliografía de referencia

Cairo, O. y Guardati, S. (s/f). Estructura de datos. https://www.udocz.com/read/23195/estructuras-

de-datos---cairo-y-guardati-3ra-edicion-pdf

Ingeniería de Software (s/f). Material no publicado.

Paszniuk, R. (s/f). Programación. https://www.programacion.com.py/

Bibliografía obligatoria

Ingeniería de Software (s/f). Material no publicado.

C O NT I NU A R
88

Descarga del contenido

¿Quieres imprimir el contenido del módulo?

Para descargar el contenido del módulo, e imprimirlo, haz clic en el archivo que se encuentra a continuación.